0%

leetcode每日一题-表示数值的字符串

Posted on In ,

表示数值的字符串

image1

有限状态自动机

image2

1
class Solution {
2
    public boolean isNumber(String s){
3
        Map[] status = {
4
                new HashMap<>() {{put(' ', 0); put('d', 2); put('s', 1); put('.', 8);}}, //0
5
                new HashMap<>() {{put('d', 2); put('.', 8);}},                           //1
6
                new HashMap<>() {{put('d', 2); put('.', 3); put('e', 4); put(' ', 7);}}, //2
7
                new HashMap<>() {{put('d', 3); put('e', 4); put(' ', 7);}},              //3
8
                new HashMap<>() {{put('s', 5); put('d', 6);}},                           //4
9
                new HashMap<>() {{put('d', 6);}},                                        //5
10
                new HashMap<>() {{put('d', 6); put(' ', 7);}},                           //6
11
                new HashMap<>() {{put(' ', 7);}},                                        //7
12
                new HashMap<>() {{put('d', 3);}}                                         //8
13
        };
14
15
        int p = 0;
16
        for(int i=0; i<s.length(); i++){
17
            char c = s.charAt(i);
18
            if(c >= '0' && c<='9'){
19
                c = 'd';
20
            }else if(c=='+' || c=='-'){
21
                c = 's';
22
            }else if(c=='e' || c=='E'){
23
                c = 'e';
24
            }
25
            if(!status[p].containsKey(c)){
26
                return false;
27
            }else{
28
                p = (int)status[p].get(c);
29
            }
30
        }
31
        return p==2 || p==3 || p==6 || p==7;
32
33
    }
34
}

复杂度分析：

  • 时间复杂度：$O(N)$。
  • 空间复杂度：$O(1)$。