Leetcode 65 Valid Number DFA有限狀態(tài)機(jī)
來源:程序員人生 發(fā)布時(shí)間:2016-09-26 08:06:51 閱讀次數(shù):3527次
Validate if a given string is numeric.
Some examples:
"0"
=> true
" 0.1 "
=> true
"abc"
=> false
"1 a"
=> false
"2e10"
=> true
Note: It is intended for the problem statement to be ambiguous. You should gather all requirements up front before implementing one.
Update (2015-02⑴0):
The signature of the C++
function had been updated. If you still see your function
signature accepts a const char *
argument, please click the reload button to
reset your code definition.
判斷數(shù)字的合法性
剛開始是把它作為1道細(xì)節(jié)較多的摹擬題做的,通過后去discuss看了1下,果然有優(yōu)美的解答!
用有限狀態(tài)機(jī)DFA解決,將每位看成1種狀態(tài)轉(zhuǎn)移條件,每次讀取的1位,就根據(jù)轉(zhuǎn)移矩陣進(jìn)行狀態(tài)轉(zhuǎn)移,若轉(zhuǎn)移到不合法的狀態(tài)則返回false。
思路簡單優(yōu)美,不用斟酌過剩的細(xì)節(jié)問題,刷了這么多l(xiāng)eetcode,這題真的眼前1亮!
具體的狀態(tài)說明可以看這篇博客
class Solution {
public:
bool isNumber(string s) {
int mp[9][6]={
{⑴, 0, 1, 2, ⑴, 3},
{⑴, ⑴, ⑴, 2, ⑴, 3},
{⑴, ⑴, ⑴, ⑴, ⑴, 4},
{⑴, 5, ⑴, 4, 6, 3},
{⑴, 5, ⑴, ⑴, 6, 4},
{⑴, 5, ⑴, ⑴, ⑴, ⑴},
{⑴, ⑴, 7, ⑴, ⑴, 8},
{⑴, ⑴, ⑴, ⑴, ⑴, 8},
{⑴, 5, ⑴, ⑴, ⑴, 8}
};
int now=0;
for(int i=0;i<s.size();i++)
{
switch(s[i])
{
case '-': now=mp[now][2];break;
case '+': now=mp[now][2];break;
case ' ': now=mp[now][1];break;
case '.': now=mp[now][3];break;
case 'e': now=mp[now][4];break;
case 'E': now=mp[now][4];break;
default:
{
if(s[i]>='0' && s[i]<='9')
now=mp[now][5];
else
now=mp[now][0];
}
}
if(now==⑴) return false;
}
return now==3 || now==4 || now==5 || now==8 ;
}
};
生活不易,碼農(nóng)辛苦
如果您覺得本網(wǎng)站對(duì)您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈(zèng)