65. Valid Number

发表于 | 分类于

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.

解法1： DFA

第一次遇到可以用DFA(finite automata)做的题，终于学到的理论知识也有可以用的地方了。
用dfa做的时候的点在于首先要换出图，然后识别出valid的state,最后判断一下是否落在state中就可以了。实现起来比较简单。
chart

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
    public boolean isNumber(String s) {
        if (s == null || s.length() == 0 || s.trim().length() == 0) {
            return false;
        }
        s = s.trim();
        int state = 1;
        boolean hasNum = false;
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (Character.isDigit(ch)) {
                hasNum = true;
                if (state <= 3) {
                    state = 3;
                } else if (state <= 5) {
                    state = 5;
                } else if (state <= 8) {
                    state = 8;
                }
            } else if (ch == '.') {
                if (state < 3) state = 4;
                else if (state == 3) state = 5;
                else return false;
            } else if (ch == 'e') {
                if (state == 3) state = 6;
                else if (state == 5) state = 6;
                else return false;
            } else if (ch == '+' || ch == '-') {
                if (state == 1) state = 2;
                else if (state == 6) state = 7;
                else return false;
            } else {
                return false;
            }
        }
        return state == 3 || state == 5 || state == 8;
    }
}