题目：
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.
链接： http://leetcode.com/problems/valid-number/
题解：
看到这种题目第一反应就是DFA了，不过怎么构建好的DFA真的很难。参考了leetcode讨论版。 Automata的知识还要好好学习学习，希望年底前还有时间。
首先对字符串进行trim，去除前后的space。之后构建DFA。输入有五种情况
- 0 - 9
- +, -
- e
- dot
- other
其中dot有种特殊情况， 就是 1.成立，但 .不成立，所以对有没有数字使用一个boolean变量来记录。 应该还可以再简化，要再研究研究。
Time Complexity - O(n)， Space Complexity - O(1)。
public class Solution {
public boolean isNumber(String s) {
if(s == null || s.length() == 0)
return false;
s = s.trim();
int state = 0;
boolean hasNum = false;
for(int i = 0; i < s.length(); i++) {
if(s.charAt(i) >= '0' && s.charAt(i) <= '9') {
hasNum = true;
if(state <= 2)
state = 2;
else
state = (state <= 5) ? 5 : 7;
} else if(s.charAt(i) == '+' || s.charAt(i) == '-') {
if(state == 0 || state == 3)
state++;
else
return false;
} else if (s.charAt(i) == '.') {
if(state <= 2)
state = 6;
else
return false;
} else if (s.charAt(i) == 'e') {
if(state == 2 || (hasNum && state == 6) || state == 7)
state = 3;
else
return false;
} else
return false;
}
return (state == 2 || state == 5 || (hasNum && state == 6) || state == 7);
}
}
Test cases:
通过以下的例子我们可以看出，对dot我们需要额外判断，比如
"+.5e-5" - True
"+5." - True
"5e-10.6" - False 使用科学计数法以后不可以出现 dot
".5e10" - True
".e10" - False
"." - False
"+5.e10" - True
二刷：
还是用state machine，画图的方法。我们详细地分解一下每个步骤。
- 首先还是上面的图， 我们先对s进行trim操作，去除头尾的空格space
- 设置一个变量hasNum来判断在string中是否曾经出现过数字，这个对于判断state 6的dot很关键
- 从0开始遍历string，根据state machine写code，假设c为当前字符，我们考虑以下情况
- 当c为数字
- 当c为'+'或者'-'
- 当c为'.'
- 当c为'e'， 这时要注意从s6到s3这条， 这里的条件为 state = s6 && hasNum，这样才可以进入s3
- 其他返回false
- 最后判断state是否在2, 5, 7以及 (state == 6 && hasNum)
Java:
Time Complexity - O(n)，Space Complexity - O(1)
public class Solution {
public boolean isNumber(String s) {
if (s == null || s.length() == 0) {
return false;
}
s = s.trim();
int state = 0;
boolean hasNum = false;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c >= '0' && c <= '9') {
hasNum = true;
if (state <= 2) {
state = 2;
} else {
state = (state <= 5) ? 5 : 7;
}
} else if (c == '+' || c == '-') {
if (state == 0 || state == 3) {
state++;
} else {
return false;
}
} else if (c == '.') {
if (state <= 2) {
state = 6;
} else {
return false;
}
} else if (c == 'e') {
if (state == 2 || state == 7 || (state == 6 && hasNum)) {
state = 3;
} else {
return false;
}
} else {
return false;
}
}
return state == 2 || state == 5 || state == 7 || (state == 6 && hasNum);
}
}
三刷:
依然是画图使用state machine的方法。 上面的图有一个地方画错了， state 6的时候，不应该有一条自己连自己的链。需要找到一种更好的办法描述state 6的终止条件，和跳到state 3的条件。 state 6跳到state 3需要 hasNum + exp， 而终止时需要hasNum。
Java:
public class Solution {
public boolean isNumber(String s) {
if (s == null || s.length() == 0) return false;
s = s.trim();
int state = 0;
boolean hasNum = false;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (Character.isDigit(c)) {
hasNum = true;
if (state <= 2) state = 2;
else if (state < 5) state = 5;
else if (state == 6) state = 7;
} else if (c == '.') {
if (state < 3) state = 6;
else return false;
} else if (c == 'e') {
if (state == 2 || (state == 6 && hasNum) || state == 7) state = 3;
else return false;
} else if (c == '+' || c == '-'){
if (state == 0 || state == 3) state++;
else return false;
} else {
return false;
}
}
return state == 2 || state == 5 || state == 7 || (state == 6 && hasNum);
}
}
Reference:
http://postimg.org/image/n7lsslmgz
https://leetcode.com/discuss/13691/c-my-thought-with-dfa
https://leetcode.com/discuss/55915/lol-hard-to-understand-but-fast-8ms
https://leetcode.com/discuss/9013/a-simple-solution-in-cpp
https://leetcode.com/discuss/26682/clear-java-solution-with-ifs
https://leetcode.com/discuss/23447/a-clean-design-solution-by-using-design-pattern
https://leetcode.com/discuss/70510/a-simple-solution-in-python-based-on-dfa
https://leetcode.com/discuss/47396/ac-java-solution-with-clear-explanation