背景描述

有效数字(按顺序)可以分成以下几个部分:

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

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

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;
    }
}