字符串处理，确定有限状态自动机

题目链接-来源：力扣（LeetCode）

请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。

数值（按顺序）可以分成以下几个部分：

若干空格
一个 小数 或者 整数
（可选）一个 ‘e’ 或 ‘E’ ，后面跟着一个 整数
若干空格
小数（按顺序）可以分成以下几个部分：

（可选）一个符号字符（’+’ 或 ‘-‘）
下述格式之一：
至少一位数字，后面跟着一个点 ‘.’
至少一位数字，后面跟着一个点 ‘.’ ，后面再跟着至少一位数字
一个点 ‘.’ ，后面跟着至少一位数字
整数（按顺序）可以分成以下几个部分：

（可选）一个符号字符（’+’ 或 ‘-‘）
至少一位数字
部分数值列举如下：

[“+100”, “5e2”, “-123”, “3.1416”, “-1E-16”, “0123”]
部分非数值列举如下：

[“12e”, “1a3.14”, “1.2.3”, “+-5”, “12e+5.4”]

示例 1：

输入：s = “0”
输出：true

思路：

注意到字符串有很多状态和可能，如果一个一个用 if-else 类似硬编码的方式处理本题，代码会相当繁琐，于是考虑引入有限状态自动机来解决此类问题。
我们可以比较容易地写出虽然冗长但是清晰的状态转移表：
前导 符号 整数 小数 指数 指数 指数 结尾 错误
空格 开始 符号 空格
输入字符 状态 start numPZ numZ numD numES numPE numE end f
‘ ‘ start f f f f f f end f
‘+’,’-‘ numPZ f f f numPE f f f f
‘.’ numD numD numD f f f f f f
‘$’数字 numZ numZ numZ numD numE numE numE f f
‘e’,’E’ f f numESnumES f f f f f
其中缺少了对单独小数点 ‘.’ 并非数字的判断，可以加在自动机状态中单列一个状态，也可以像我一样额外设计一个方法 isDecimal() 判断当前收集到的字符串是否为小数。
时间复杂度：O(n)
空间复杂度：O(1)

实现：

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
class Solution {
    private Map<String, String[]> map = new HashMap<>() {{
            put("start", new String[] {"start", "numPZ", "numZ", "numD", "numES", "numPE", "numE", "end", "false"});
            put("numPZ", new String[] {"start", "numPZ", "numZ", "numD", "numES", "numPE", "numE", "end", "false"});
            put("numZ", new String[] {"start", "numPZ", "numZ", "numD", "numES", "numPE", "numE", "end", "false"});
            put("numD", new String[] {"start", "numPZ", "numZ", "numD", "numES", "numPE", "numE", "end", "false"});
            put("numES", new String[] {"start", "numPZ", "numZ", "numD", "numES", "numPE", "numE", "end", "false"});
            put("numPE", new String[] {"start", "numPZ", "numZ", "numD", "numES", "numPE", "numE", "end", "false"});
            put("numE", new String[] {"start", "numPZ", "numZ", "numD", "numES", "numPE", "numE", "end", "false"});
            put("end", new String[] {"start", "numPZ", "numZ", "numD", "numES", "numPE", "numE", "end", "false"});
        }};
    
    public boolean isNumber(String s) {
        int len = s.length();
        String status = "start";
        String fail = "false";
        for (int i = 0; i < len; i++) {
            char c = s.charAt(i);
            status = map.get(status)[getCol(status, c)];
            
            if (status.equals(fail)) {
                return false;
            }
            
            if (c == '.' && !isDecimal(s, i)) {
                return false;
            }
            
        }
        
        if (status.equals("numZ") || status.equals("numD") || status.equals("numE") || status.equals("end")) {
            return true;
        } else {
            return false;
        }
    }
    
    private boolean isDecimal (String s, int dotIndex) {
        int len = s.length();
        if (dotIndex > 0 && s.charAt(dotIndex - 1) >= '0' && s.charAt(dotIndex - 1) <= '9') {
            return true;
        } 
        if (dotIndex < len - 1 && s.charAt(dotIndex + 1) >= '0' && s.charAt(dotIndex + 1) <= '9') {
            return true;
        }
        return false;
    }
    
    private int getCol(String status, char c) {
        int i;
        int j;
        switch(c) {
            case ' ':
                i = 0;
                break;
            case '+': case '-':
                i = 1;
                break;
            case '.':
                i = 2;
                break;
            case '0': case '1': case '2': case '3': case '4': case '5': case '6': case '7': case '8': case '9':
                i = 3;
                break;
            case 'e': case 'E':
                i = 4;
                break;
            default:
                i = 5;
        }
        
        switch(status) {
            case "start":
                j = 0;
                break;
            case "numPZ":
                j = 1;
                break;
            case "numZ":
                j = 2;
                break;
            case "numD":
                j = 3;
                break;
            case "numES":
                j = 4;
                break;
            case "numPE":
                j = 5;
                break;
            case "numE":
                j = 6;
                break;
            case "end":
                j = 7;
                break;
            default:
                j = 8;
        }
        
        return move[i][j];
    }
    
    private int[][] move = new int[][] {
        {0, 8, 7, 7, 8, 8, 7, 7, 8}, 
        {1, 8, 8, 8, 5, 8, 8, 8, 8},
        {3, 3, 3, 8, 8, 8, 8, 8, 8},
        {2, 2, 2, 3, 6, 6, 6, 8, 8},
        {8, 8, 4, 4, 8, 8, 8, 8, 8},
        {8, 8, 8, 8, 8, 8, 8, 8, 8}
    };
}