背景描述

有效数字（按顺序）可以分成以下几个部分：

  1. 一个 小数 或者 整数
  2. （可选）一个 ’e’ 或 ‘E’ ，后面跟着一个 整数

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

  • （可选）一个符号字符（’+’ 或 ‘-’）
  • 下述格式之一：
    1. 至少一位数字，后面跟着一个点 ‘.’
    2. 至少一位数字，后面跟着一个点 ‘.’ ，后面再跟着至少一位数字
    3. 一个点 ‘.’ ，后面跟着至少一位数字

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

  • （可选）一个符号字符（’+’ 或 ‘-’）
  • 至少一位数字

部分有效数字列举如下：
["2", "0089", "-0.1", "+3.14", "4.", "-.9", "2e10", "-90E3", "3e+7", "+6e-1", "53.5e93", "-123.456e789"]

部分无效数字列举如下：
["abc", "1a", "1e", "e3", "99e2.5", "--6", "-+3", "95a54e53"]

提示
1 <= s.length <= 20
s 仅含英文字母（大写和小写），数字（0-9），加号 ‘+’ ，减号 ‘-’ ，或者点 ‘.’ 。

模拟

这种方式就是按照字符串的规律，写对对应的代码，来判断输入的字符串是否正确
模拟过程如下：

  1. 去掉开头、结尾的空格符(这步可以省略，按照提示字符串不包含空格)
  2. 如果是空串直接返回错误
  3. 判断开头的 + -，如果(+-)后面是空，则返回错误
  4. 处理数字和小数部分
    • 如果小数点的个数 > 1，则返回错误
    • 如果小数点个数 <= 1，判断数字数量是否 > 0
  5. 处理指数部分
    • 这时候，还要判断下如果有指数e时，小数点>1 或 数字数量为0，则错误
    • 处理 + - 部分
    • 处理数字部分
    • 判断剩余部分

代码如下：

 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

class Solution(object):
    def isNumber(self, s):
        if not s:
            return False
        n = len(s)
        i = 0
        j = n-1
        while i<n and s[i]==" ":
            i += 1
        while j>=0 and s[j]==" ":
            j -= 1
        s = s[i:j+1]
        if not s:
            return False
        letter = set(['0', '1', '2', '3', '4', '5', '6', '7', '8', '9'])
        n = len(s)
        i = 0
        if s[i] in ("-","+"):
            i += 1
            if i==n:
                return False
        letter.add(".")
        dot_num = 0
        digit_num = 0
        while i<n and s[i] in letter:
            if s[i]==".":
                dot_num += 1
            else:
                digit_num += 1
            i += 1
        if i==n:
            if dot_num<=1:
                return digit_num>0
            else:
                return False
        letter.remove(".")
        if s[i]=="e":
            if dot_num>1 or digit_num==0:
                return False
            i += 1
            if i==n:
                return False
            if s[i] in ("-","+"):
                i += 1
                if i==n:
                    return False
            digit_num = 0
            while i<n and s[i] in letter:
                digit_num += 1
                i += 1
            if i==n:
                if digit_num==0:
                    return False
                return True
            else:
                return False
        else:
            return False

也可以用正则来实现

1
2
3

class Solution(object):
    def isNumber(self, s):
        return bool(re.match(r'[+-]?(\d+)?\.?(?(1)\d*|\d+)([eE][+-]?\d+)?$', s))

DFA

这里需要用到编译原理的知识，用状态机来解析一个个的token
状态机有两种

  • 非确定的有限自动机(Nondeterministic Finite Automaton，NFA)
  • 确定的有限自动机(Deterministic Finite Automaton，DFA)

NFA占用内存小，但是效率差些，会出现回溯
DFA占用内存大，但是效率高，不会有回溯

我们来构造出DFA状态机(可以根据正则表达式构造)，如下图：
1 上图中橙色节点是终止状态，也就当字符串遍历完后，位于这个状态下，就表示正确结束，返回true
如果是处于蓝色节点，就是中间状态，返回false
这里初始状态为0，终止状态为2、4、7
如果输入的字符串是合法的，那么从0开始出发，不管中间怎么转换，当字符串遍历结束后，最终一定会落到状态2、4、7其中之一

之后，再根据状态机构造出跳转表，这个跳转表就等价于程序中用到的二维数组
跳转表如下：

state +- 0-9 . eE other
0 1 2 3 -1 -1
1 -1 2 3 -1 -1
2 -1 2 4 5 -1
3 -1 4 -1 -1 -1
4 -1 4 -1 5 -1
5 6 7 -1 -1 -1
6 -1 7 -1 -1 -1
7 -1 7 -1 -1 -1

上述表格中的0 - 7就对应了图中的各个状态
当在状态2时，遇到.就跳转到状态3，于是在表格中对应的行和列中填3
当状态3时，遇到0-9就跳转到状态4，于是在表格中对应的行和列中填4

将上述的表格保存为一个二维数组arr，第一列的state去掉
+-对应第0列、0-9对应第1、.对应底2列
eE对应底3列，其他字符对应底4列
然后根据当前状态，当前状态下的字符做跳转，比如：

  • 当前状态0，字符为 . ，也就是查找arr[0][3]，跳转到状态3
  • 当前状态2，字符为8，查找arr[2][2]，再次跳转到状态2

我们以-12.34E56来说明上述的跳转表是如何工作的

  1. - 对应第0列，arr[0][0] -> 状态 1
  2. 1 对应第1列，arr[1][1] -> 状态 2
  3. 2 对应第1列，arr[2][1] -> 状态 2
  4. . 对应第2列，arr[2][2] -> 状态 4
  5. 3 对应第1列，arr[4][1] -> 状态 4
  6. 4 对应第1列，arr[4][1] -> 状态 4
  7. E 对应第3列，arr[4][3] -> 状态 5
  8. 5 对应第1列，arr[5][1] -> 状态 7
  9. 6 对应第1列，arr[7][1] -> 状态 7
  10. 字符串遍历结束，当前状态为7，是终止状态，匹配成功

代码如下：

 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

class Solution {
    private static final int[][] transformTable = new int[][]{
            //跳转表，第0对应'+-'、第1列对应'0-9'、第2列对应'.'   
            //第三列对应'eE'，第4列对应其他字符
            {1,2,3,-1,-1},
            {-1,2,3,-1,-1},
            {-1,2,4,5,-1},
            {-1,4,-1,-1,-1},
            {-1,4,-1,5,-1},
            {6,7,-1,-1,-1},
            {-1,7,-1,-1,-1},
            {-1,7,-1,-1,-1}
    };

    public boolean isNumber(String s) {
        char[] charArray = s.toCharArray();
        int stateID = 0;
        int tokenID = -1;
        for(int i = 0; i < charArray.length; ++i) {
            char c = charArray[i];
            //当前字符 c 对应到二维数组中的哪一列
            switch(c) {
                case '+': case '-': tokenID = 0; break;
                case '.': tokenID = 2; break;
                case 'e': case 'E': tokenID = 3; break;
                default:
                    if(c >= '0' && c <= '9') tokenID = 1;
                    else tokenID = -1;
            }
            //当前的token为-1，或者下一步跳转的状态为-1时，可以提前返回false
            if(tokenID == -1) return false;
            //根据当前状态，当前的字符类型，去二维表格中查询下一步跳转到哪个状态
            stateID = transformTable[stateID][tokenID];
            if(stateID == -1) return false;
        }
        //字符串遍历结束，看当前状态是否为终止状态
        return stateID == 2 || stateID == 4 || stateID == 7;
    }
}