Validate if a given string is numeric.
Some examples:
"0" => true
" 0.1 " => true
"abc" => false
"1 a" => false
"2e10" => true
http://www.jiuzhang.com/solutions/valid-number/
https://leetcodenotes.wordpress.com/2013/11/23/leetcode-valid-number/
Use DFA(Deterministic Finite Automata)
Code from http://jelices.blogspot.com/2013/12/leetcode-valid-number.html
We accept the following regular grammar, shown as UNIX regular expression by simplicity:
\s*[\+\-]?(([0-9]+(\.[0-9]*)?)|\.[0-9]+)([eE][+-]?[0-9]+)?\s*
where \s represents [ \t].
This regular expression is accepted by the underneath DFA(Deterministic Finite Automata):
Use Regular Expression:
Code from http://www.cnblogs.com/midnightcat/p/3364431.html
http://blog.csdn.net/kenden23/article/details/18696083
Read full article from LeetCode - Valid Number | Darren's Blog
Some examples:
"0" => true
" 0.1 " => true
"abc" => false
"1 a" => false
"2e10" => true
http://www.jiuzhang.com/solutions/valid-number/
public boolean isNumber(String s) { int len = s.length(); int i = 0, e = len - 1; while (i <= e && Character.isWhitespace(s.charAt(i))) i++; if (i > len - 1) return false; while (e >= i && Character.isWhitespace(s.charAt(e))) e--; // skip leading +/- if (s.charAt(i) == '+' || s.charAt(i) == '-') i++; boolean num = false; // is a digit boolean dot = false; // is a '.' boolean exp = false; // is a 'e' while (i <= e) { char c = s.charAt(i); if (Character.isDigit(c)) { num = true; } else if (c == '.') { if(exp || dot) return false; dot = true; } else if (c == 'e') { if(exp || num == false) return false; exp = true; num = false; } else if (c == '+' || c == '-') { if (s.charAt(i - 1) != 'e') return false; } else { return false; } i++; } return num; }https://discuss.leetcode.com/topic/9490/clear-java-solution-with-ifs
All we need is to have a couple of flags so we can process the string in linear time:
We start with trimming.
- If we see
[0-9]we reset the number flags. - We can only see
.if we didn't seeeor.. - We can only see
eif we didn't seeebut we did see a number. We reset numberAfterE flag. - We can only see
+and-in the beginning and after ane - any other character break the validation.
At the and it is only valid if there was at least 1 number and if we did see an
e then a number after it as well.
So basically the number should match this regular expression:
[-+]?[0-9]*(.[0-9]+)?(e[-+]?[0-9]+)?public boolean isNumber(String s) {
s = s.trim();
if (s.length() > 0 && s.charAt(s.length() - 1) == 'e')
return false; //avoid "3e" which is false
String[] t = s.split("e");
if (t.length == 0 || t.length > 2)
return false;
boolean res = valid(t[0], false);
if (t.length > 1)
res = res && valid(t[1], true);
return res;
}
private boolean valid(String s, boolean hasDot) { // how about change to canHaveDot, valid(t[0], true), valid(t[1], false)
if (s.length() > 0 && (s.charAt(0) == '+' || s.charAt(0) == '-')) //avoid "1+", "+", "+."
s = s.substring(1);
char[] arr = s.toCharArray();
if (arr.length == 0 || s.equals("."))
return false;
for (int i = 0; i < arr.length; i++) {
if (arr[i] == '.') {
if (hasDot)
return false;
hasDot = true;
} else if (!('0' <= arr[i] && arr[i] <= '9')) {
return false;
}
}
return true;
}
public boolean isNumber(String s) {
s = s.trim(); // Get rid of leading and trailing whitespaces
int n = s.length();
if (n == 0)
return false;
boolean isFractional = false; // Indicate appearance of '.'
boolean isExponential = false; // Indicate appearance of 'e/E'
boolean valid = false; // Indicate whether preceding digits are valid
boolean expoBefore = false; // Indicate whether the preceding digit is 'e/E'
boolean validFrac = true; // Indicate whether the number is a vaild fraction (true by default)
boolean validExpo = true; // Indicate whether the number is a valid exponential (true by default)
int i = 0;
if (s.charAt(0) == '+' || s.charAt(0) == '-') // Consider sign
i = 1;
// Process each digit in sequence
for (; i < n; i++) {
char c = s.charAt(i);
if (c == '+' || c == '-') { // +/- is valid only after e/E
if (!expoBefore)
return false;
expoBefore = false;
valid = false;
} else if (c == 'e' || c == 'E') { // Only one e/E is valid; preceding digits should be valid
if (isExponential || !valid)
return false;
isExponential = true;
valid = false;
expoBefore = true;
validExpo = false;
} else if (c == '.') { // Only one '.' is valid; cannot appear as an exponential
if (isFractional || isExponential)
return false;
isFractional = true;
if (!valid) // Must have fractional part
validFrac = false;
} else if (c >= '0' && c <='9') { // Regular digits
valid = true;
expoBefore = false;
validFrac = true;
validExpo = true;
} else {
return false;
}
}
// After reaching the end, make sure the number is indeed valid
if (!valid || !validFrac || !validExpo)
return false;
else
return true;
}
https://discuss.leetcode.com/topic/8029/a-clean-design-solution-by-using-design-patternUse DFA(Deterministic Finite Automata)
Code from http://jelices.blogspot.com/2013/12/leetcode-valid-number.html
We accept the following regular grammar, shown as UNIX regular expression by simplicity:
\s*[\+\-]?(([0-9]+(\.[0-9]*)?)|\.[0-9]+)([eE][+-]?[0-9]+)?\s*
where \s represents [ \t].
This regular expression is accepted by the underneath DFA(Deterministic Finite Automata):
public boolean isNumber(String s) { int state = 0; for(int i=0; i<s.length();i++) { state=getNextState(state, s.charAt(i)); if (state==-1) return false; } state = getNextState(state, ' '); return state == 8; } private int getNextState(int state, char c) { int[][] transitionTable = { {0,2,1,3,-1,-1}, {-1,2,-1,3,-1,-1}, {8,2,-1,4,5,-1}, {-1,4,-1,-1,-1,-1}, {8,4,-1,-1,5,-1}, {-1,7,6,-1,-1,-1}, {-1,7,-1,-1,-1,-1}, {8,7,-1,-1,-1,-1}, {8,-1,-1,-1,-1,-1}}; return transitionTable[state][getSymbol(c)]; } private int getSymbol(char c) { switch(c) { case ' ': case '\t': return 0; case '0': case '1': case '2':case '3': case '4': case '5': case '6': case '7': case '8': case '9': return 1; case '+': case '-': return 2; case '.': return 3; case 'E': case 'e': return 4; default: return 5; } }http://noalgo.info/995.html
此题使用一般的判断非常繁琐，极其容易出错，但是可以使用有限状态机进行解决，思路较为直接，而且代码非常简短。
考虑所有可能的输入，不同的输入会导致状态的不同转移，把每种输入用一个数字进行表示如下：
- 0：非法字符
- 1：空格
- 2：正负号
- 3：小数点
- 4：指数e
- 5：数字
令状态S0为初始状态，考虑其在不同输入下的转移情况。
- 0：数字带有非法字符，非法。转入非法状态，用状态-1表示。
- 1：数字带有前导空格，合法。新状态和初始状态一样，转入状态0。
- 2：数字带有正负号，合法。此时需要进入一个新的状态，用状态1表示（内容仅含正负号）。
- 3：数字一开始即为小数点，合法，因为有如.1之类的数字。需要转入一个新的状态，用状态2表示（内容仅含小数点）。
- 4：数字一开始即为指数e，非法。转入非法状态-1。
- 5：数字一开始即为数字，合法。需要转入新状态，用状态3表示（内容仅含数字）。
为了方便，只需要考虑所有合法的转移即可，下面是状态0的含义及转移情况。状态0为初始状态，可以有空格。
- 1->0：输入空格，转入自身。
- 2->1：输入正负号，转入新状态1（仅含正负号）。
- 3->2：输入小数点，转入新状态2（仅含小数点）。
- 5->3：输入数字，转入新状态3（仅含数字）。
下面考虑状态1。状态1仅含有一个正负号，后面只允许接小数点或者数字。
- 3->2：接小数点，新状态变为正负号+小数点，可以和状态2合并，转入新状态2（[正负号] + 小数点）。
- 5->3：接数字，新状态变为正负号+数字，可以和状态3合并，转入新状态3（[正负号] + 数字）。
下面考虑状态2。状态2包含一个小数点，前面可能含有正负号，[正负号] + 小数点。此时后面只允许接数字。
- 5->4：接数字，转入新状态4（[正负号] + 小数点 + 数字）。
下面考虑状态3。状态3包含数字，前面可能有正负号，[正负号] + 数字。此时后面只允许接空格、小数点、指数e或者数字。
- 1->4：接空格，转入新状态5（合法数字 + 空格）。
- 3->4：接小数点，此时状态为数字加小数点，由于形如3.的数字也是合法数字，可以转入状态4（[正负号] + 数字 + 小数点）。
- 4->6：接指数e，转入新状态6,（不带e的合法数字 + e）。
- 5->3：接数字，转入自身。
下面考虑状态4。状态4为[正负号] + 小数点 + 数字，或者[正负号] + 数字 + 小数点，本质上是一个合法的不带e的数字。其后面可以继续接数字，也可以接空格，指数e。
- 1->5：接空格，转入状态5。
- 4->6：接指数e，转入状态6。
- 5->4：接数字，转入自身。
下面考虑状态5。状态5为一个合法数字接空格，为后导空格情况，此时只允许出现空格字符。
- 1->5：接空格，转入自身。
下面考虑状态6。状态6为一个不带e的合法数字接e的情况，此时后面只允许出现正负号或者数字。
- 2->7：接正负，转入新状态7（不带e的合法数字 + e + 正负号）。
- 5->8：接数字，转入新状态8（不带e的合法数字 + e + 数字）。
下面考虑状态7。状态7为 不带e的合法数字 + e + 正负号，此时后面只允许接数字。
- 5->8：接数字，转入状态8，状态8变为 不带e的合法数字 + e + [正负号] + 数字
下面考虑状态8:。状态8为 不带e的合法数字 + e + [正负号] + 数字，其后面只能够接数字，或者空格。
- 1->5：接空格，转入状态5。
- 5->8：接数字，转入自身。
此时，所有的状态已经考虑完毕，可以得到以下状态转换矩阵trans：
其中trans[i][j]即表示从状态i接受输入j进入的新状态。
还有最后一个问题，自动机中的哪些状态是合法的呢？根据合法数字的定义可以容易知道，状态3、4、5、8是合法状态。
现在可以轻松得到程序的代码了。
http://noalgo.info/993.html
判断一个字符串是否是一个合法的数字。这题非常繁琐，需要考虑的细节非常多，这里罗列如下：
- 字符串是否为NULL。
- 数字不能有非法字符。
- 数字可能带有前导空格和最后面的空格，中间不能有空格。
- 数字可能带有显示的+号或者-号，但又不能只有正负号。
- 数字可能带有小数点，但只能有一个小数点，小数点后至少要有一个数字。
- 数字可能带有e表示10的幂次，e后至少有一个数字，但该数字可以带正负号，但又不能只有正负号。
- 数字不能同时有e和小数点。
Use Regular Expression:
Code from http://www.cnblogs.com/midnightcat/p/3364431.html
Pattern p = Pattern.compile("^[\\+\\-]?((\\d+(\\.\\d*)?)|(\\.\\d+))(e[\\+\\-]?\\d+)?$"); public boolean isNumber(String s) { String ss = s.trim(); return p.matcher(ss).matches(); }Also refer to http://blog.csdn.net/ithomer/article/details/8832300
http://blog.csdn.net/kenden23/article/details/18696083
Read full article from LeetCode - Valid Number | Darren's Blog
