前往
大廳
主題

LeetCode - 65. Valid Number 解題心得

Not In My Back Yard | 2021-06-12 00:00:01 | 巴幣 0 | 人氣 189

題目連結:


題目意譯:
一個合法的數字可以被分成以下部分(依照順序):
1.一個小數或是一個整數。
2.(非必要的)一個 'e' 或是 'E',其後跟著一個整數。

一個小數可以被分成以下部分(依照順序):
1.(非必要的)一個正負符號(只會是 '+' 或是 '-')。
2.以下格式之一:
    1.至少一位數,其後跟著一個小數點 '.'。
    2.至少一位數,其後跟著一個小數點 '.',再其後跟著至少一位數。
    3.一個小數點 '.',其後跟著至少一位數。

一個整數可以被分成以下部分:
1.(非必要的)一個正負符號(只會是 '+' 或是 '-')。
2.至少一位數。

例如,以下全是合法的數字:["2", "0089", "-0.1", "+3.14", "4.", "-.9", "2e10", "-90E3", "3e+7", "+6e-1", "53.5e93", "-123.456e789"];而以下這些則不是合法的數字:["abc", "1a", "1e", "e3", "99e2.5", "--6", "-+3", "95a54e53"]。

給定一個字串 s ,回傳真(True)如果 s 是一個合法數字。

限制:
1 ≦ s.length ≦ 20
s 只由英文字母組成(大小寫都有可能)、數字(0 ~ 9)、加號 '+' 、減號 '-' 或是小數點 '.'。



範例測資:
範例 1:
輸入: s = "0"
輸出: true

範例 2:
輸入: s = "e"
輸出: false

範例 3:
輸入: s = "."
輸出: false

範例 4:
輸入: s = ".1"
輸出: true


解題思維:
如果要照著題目敘述直接寫一堆 if 和 for 一定會是一件吃力的工作。

不過,我們有一種工具叫做正規表達式(Regular Expression)。用以匹配一些資料時會是相當強大的工具,例如匹配密碼是否符合命名規則,或是像本題判斷數字合不合法等等。

而在 C++11 的標準函式庫裡引入了正規表達式標頭檔 <regex> (Python 內建也有,函式庫名字是 re)。順帶一提,Lambda 語法以及空指標 nullptr 也是這個時期引入的。

本題只需要使用其宣告法以及 regex_match() 函式。因此本題只需在原本的類別程式碼加上
    static const regex matchingRule(R"_([+-]?((\d+(\.\d*)?)|(\.\d+))([Ee][+-]?\d+)?)_");
    return regex_match(s, matchingRule);
兩條程式碼即可完成。

簡單來說,第一列是宣告(匹配規則是寫在這邊)、第二列就是回傳匹配結果(匹配成功即為真;反之為假)。

而我們來解析一下上面那個驚悚的
R"_([+-]?((\d+(\.\d*)?)|(\.\d+))([Ee][+-]?\d+)?)_"
之含意。

首先,這東西不是常見的 C++ 字串,其形式不是一般字串的 "" 而是 R"_(字串內容)_" 。其代表著字串內容應解讀成原始字串(Raw String),因此不需額外加上逸出字元,例如 R"_(\d\n\\123)_" 等價於一般字串 "\\d\n\\\\123"。題外話,這個也是 C++11 時引進的新特色,其名為「Raw String Literal」。

而中間的字串內容為
[+-]?((\d+(\.\d*)?)|(\.\d+))([Ee][+-]?\d+)?
其可以拆分為三個部分:
第一部分為
[+-]?
其中的「[]」在正規表達式代表著匹配存在於 [] 中的字元,像是這邊的「+」或是「-」。而「?」代表著匹配一次或是零次(代表著「非必要」的部分)。因此這個部分代表著數字前面可以有也可以沒有正負號的存在。

例如「+7」、「-8.5」等等中的「+」和「-」,而正負號可以不存在,所以「80」等數也會通過這一部份的匹配。



第二部分為
((\d+(\.\d*)?)|(\.\d+))
而其又可以細分為
(\d+(\.\d*)?)
以及
(\.\d+))
兩者中間用「|」連接起來,代表匹配其中一者即可。而最外層的「()」則是代表著這整個部分(即 (\d+(\.\d*)?)|(\.\d+)) )是一個匹配群(因為「|」不用括號框起來的話,則會將整個正規表達式一分為二成左右兩邊)。

而 (\d+(\.\d*)?) 中的「\d」等價於 [0-9] 代表匹配數字 0 ~ 9 ,當中的「\」是用來標示這邊的「d」不是字母 d 而是 [0-9]、 「+」則代表匹配一個以上(含)、「\.」代表著小數點 '.' ,前面加上「\」的理由與「\d」一樣,因為一般的「.」代表著匹配任意字元。

最後還有著「*」代表著零個以上(含),也就代表著前面要匹配的對象可以可無。

因此這邊代表著匹配小數格式之一以及之二,例如「12.」或是「8.7」等等。

而 (\.\d+)) 則代表著要匹配小數格式之三的情況,例如「.44」、「.38」等等。

因此這整個第二部分就是用來匹配小數之格式。



第三部分則是
([Ee][+-]?\d+)?
可以根據「()?」看到這一整群是可存在也可不存在的。

而中間的 [Ee][+-]?\d+ 代表著要匹配一個「e」或是「E」、可有可無的正負號,以及至少一位數的數字群。例如「1e+7」、「1E7」、「555E-888」中的「e+7」、「E7」、「E-888」之部分。

以上,我們便藉著短短的正規表達式完成了題目的要求。想要知道更多關於正規表達式的規則或是匹配能力,可以參見維基頁面




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作