Leetcode 65 Valid Number DFA有限状态机
Leetcode 65 Valid Number DFA有限状态机
triplebee
发布于 2018-01-12 15:04:56
发布于 2018-01-12 15:04:56
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-10):
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.
判断数字的合法性
刚开始是把它作为一道细节较多的模拟题做的，通过后去discuss看了一下，果然有优美的解答！
用有限状态机DFA解决，将每一位看成一种状态转移条件，每次读取的一位，就根据转移矩阵进行状态转移，若转移到不合法的状态则返回false。
思路简单优美，不用考虑多余的细节问题，刷了这么多leetcode，这题真的眼前一亮！
具体的状态说明可以看这篇博客
class Solution {
public:
bool isNumber(string s) {
int mp[9][6]={
{-1, 0, 1, 2, -1, 3},
{-1, -1, -1, 2, -1, 3},
{-1, -1, -1, -1, -1, 4},
{-1, 5, -1, 4, 6, 3},
{-1, 5, -1, -1, 6, 4},
{-1, 5, -1, -1, -1, -1},
{-1, -1, 7, -1, -1, 8},
{-1, -1, -1, -1, -1, 8},
{-1, 5, -1, -1, -1, 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==-1) return false;
}
return now==3 || now==4 || now==5 || now==8 ;
}
};本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2016-09-20 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读