原题传送门
1、思路分析
All we need is to have a couple of flags so we can process the string in liner time:
We start with trimming.
If we see [0-9]
we reset the number flags.
We can only see .
if we didn't see e
or .
We can only see e
if we didn't see e
but we did see a number. We reset numberAfterE flag.
We can only see + and - in the beginning and after an e
any other character break the validation.
At the end 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.
2、代码实现
package Q0099.Q0065ValidNumber; public class Solution { /* All we need is to have a couple of flags so we can process the string in liner time: We start with trimming. If we see `[0-9]` we reset the number flags. We can only see `.` if we didn't see `e` or `.` We can only see `e` if we didn't see `e` but we did see a number. We reset numberAfterE flag. We can only see + and - in the beginning and after an e any other character break the validation. At the end 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]*)?)|.[0-9]+)(e[-+]?[0-9]+)? The 'numberAfterE' is unnecessary. */ public boolean isNumber(String s) { s = s.trim().toLowerCase(); boolean pointSeen = false; boolean eSeen = false; boolean numberSeen = false; for (int i = 0; i < s.length(); i++) { if ('0' <= s.charAt(i) && s.charAt(i) <= '9') { numberSeen = true; } else if (s.charAt(i) == '.') { if (eSeen || pointSeen) return false; pointSeen = true; } else if (s.charAt(i) == 'e') { if (eSeen || !numberSeen) return false; numberSeen = false; eSeen = true; } else if (s.charAt(i) == '-' || s.charAt(i) == '+') { if (i != 0 && s.charAt(i - 1) != 'e') return false; } else { return false; } } return numberSeen; } }
3、复杂度分析
时间复杂度: O(n)
空间复杂度: O(1)
package Q0099.Q0065ValidNumber; public class Solution2 { public boolean isNumber(String s) { return s.trim().matches("[-+]?(\\d+\\.?|\\.\\d+)\\d*([e|E][-+]?\\d+)?"); } }
1、思路分析
DFA: Deterministic Finite Automaton 确定有限状态自动机
States
0: initial
1: only dot
2: number
3: sign
4: dot number
5: e
6: e sign
7: e number
8: end
9: fail
Inputs 0: others 1: space 2: dot 3: numbers 4: sign 5: e
2、代码实现
package Q0099.Q0065ValidNumber; import java.util.Arrays; import java.util.List; /* DFA: Deterministic Finite Automaton 确定有限状态自动机 States 0: initial 1: only dot 2: number 3: sign 4: dot number 5: e 6: e sign 7: e number 8: end 9: fail Inputs 0: others 1: space 2: dot 3: numbers 4: sign 5: e */ public class Solution3 { boolean isNumber(String s) { int state = 0; int[][] transitions = { // 0, 1, 2, 3, 4, 5 {9, 0, 1, 2, 3, 9}, // 0 {9, 9, 9, 4, 9, 9}, // 1 {9, 8, 4, 2, 9, 5}, // 2 {9, 9, 1, 2, 9, 9}, // 3 {9, 8, 9, 4, 9, 5}, // 4 {9, 9, 9, 7, 6, 9}, // 5 {9, 9, 9, 7, 9, 9}, // 6 {9, 8, 9, 7, 9, 9}, // 7 {9, 8, 9, 9, 9, 9}, // 8 {9, 9, 9, 9, 9, 9} // 9 }; for (int i = 0; i < s.length(); i++) { int input = getInput(s.charAt(i)); state = transitions[state][input]; if (state == 9) return false; } List<Integer> accepts = Arrays.asList(2, 4, 7, 8); return accepts.contains(state); } private int getInput(char c) { if (c == ' ') return 1; if (c == '.') return 2; if (c >= '0' && c <= '9') return 3; if (c == '+' || c == '-') return 4; if (c == 'e' || c == 'E') return 5; return 0; } }
3、复杂度分析
时间复杂度: O(n)
空间复杂度: O(1)