65. Valid Number
题目描述：
Validate if a given string is numeric.
Some examples:
"0" => true " 0.1 " => true "abc" => false "1 a" => false "2e10" => trueNote: It is intended for the problem statement to be ambiguous. You should gather all requirements up front before implementing one.
题目翻译
判断一个给定的字符串是否为数字。
示例：
"0" => true
" 0.1 " => true
"abc" => false
"1 a" => false
"2e10" => true
注意： 这个问题可能描述得不是很清楚。在解题之前你最好先搜集所有可能的要求。
解题方案
标签： Math
思路：
- 这道验证数字的题比想象中的要复杂的多，有很多情况需要考虑。网上有很多解法，有利用有限自动机Finite Automata Machine的程序写的简洁优雅,还有利用正则表达式。，更是写的丧心病狂的简洁。
使用确定有穷状态自动机(DFA)来解答此题必然是最优雅的，无论空间还是时间复杂度都有不错的表现。所谓“确定有穷状态”，必然需要我们自己动手构造出所有状态来，这是建立DFA 最难 的部分，因为你需要把每种状况都考虑到，如下所示：
0 初始无输入或者只有space的状态 1 输入了数字之后的状态 2 前面无数字，只输入了dot的状态 3 输入了+/-状态 4 前面有数字和有dot的状态 5 'e' or 'E'输入后的状态 6 输入e之后输入+/-的状态 7 输入e后输入数字的状态 8 前面有有效数输入之后，输入space的状态
在9种状态中，我们可以发现只有1、4、7、8四种状态是合法的，所以题目迎刃而解，只要挨个遍历字符，通过判断遍历到最后一个字符时的状态即可确定该字符串是否合法。
- 在编程中，我们可以简单地用一个邻接矩阵来存储上图转移关系。
- 时间复杂度为O(n)
代码：
class Solution {
public:
bool isNumber(string s) {
int INVALID=0; // 0 Include: Alphas, '(', '&' ans so on
int SPACE=1; // 1
int SIGN=2; // 2 '+','-'
int DIGIT=3; // 3 numbers
int DOT=4; // 4 '.'
int EXPONENT=5; // 5 'e' 'E'
int transTable[][6] = {
//0INVA,1SPA,2SIG,3DI,4DO,5E
-1, 0, 3, 1, 2, -1,//0初始无输入或者只有space的状态
-1, 8, -1, 1, 4, 5,//1输入了数字之后的状态
-1, -1, -1, 4, -1, -1,//2前面无数字，只输入了Dot的状态
-1, -1, -1, 1, 2, -1,//3输入了符号状态
-1, 8, -1, 4, -1, 5,//4前面有数字和有dot的状态
-1, -1, 6, 7, -1, -1,//5'e' or 'E'输入后的状态
-1, -1, -1, 7, -1, -1,//6输入e之后输入Sign的状态
-1, 8, -1, 7, -1, -1,//7输入e后输入数字的状态
-1, 8, -1, -1, -1, -1,//8前面有有效数输入之后，输入space的状态
};
int state = 0;
for (int i=0;i<s.size();i++)
{
int input = INVALID;
if (s[i] == ' ') input = SPACE;
else if (s[i] == '+' || s[i] == '-') input = SIGN;
else if (isdigit(s[i])) input = DIGIT;
else if (s[i] == '.') input = DOT;
else if (s[i] == 'e' || s[i] == 'E') input = EXPONENT;
state = transTable[state][input];
if (state == -1) return false;
}
if(state == 1 || state == 4 || state == 7 || state == 8) return true;
else return false;
}
};