剑指 Offer 20. 表示数值的字符串

题目

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
请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。

数值（按顺序）可以分成以下几个部分：
	1. 若干空格
	2. 一个 小数 或者 整数
	3. （可选）一个 'e' 或 'E' ，后面跟着一个 整数
	4. 若干空格
	
	
小数（按顺序）可以分成以下几个部分：
	1.（可选）一个符号字符（'+' 或 '-'）
	2. 下述格式之一：
		1. 至少一位数字，后面跟着一个点 '.'
		2. 至少一位数字，后面跟着一个点 '.' ，后面再跟着至少一位数字
		3. 一个点 '.' ，后面跟着至少一位数字
		
		
整数（按顺序）可以分成以下几个部分：
	1. （可选）一个符号字符（'+' 或 '-'）
	2. 至少一位数字
	
	
部分数值列举如下：
	["+100", "5e2", "-123", "3.1416", "-1E-16", "0123"]
部分非数值列举如下：
	["12e", "1a3.14", "1.2.3", "+-5", "12e+5.4"]
 
示例 1：
    输入：s = "0"
    输出：true
    
示例 2：
    输入：s = "e"
    输出：false
    
示例 3：
    输入：s = "."
    输出：false
示例 4：
    输入：s = "    .1  "
    输出：true
 

提示：

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

思路

使用有限状态自动机，如果不知道什么是自动机的推荐视频：https://www.bilibili.com/video/BV1uJ411Y7Eg?p=3

本题的思路就想根据字符类型和合法数值的特点，先定义状态，再画出状态转移图，最后编写代码

字符类型：

空格 「 」、数字「 0—9」 、正负号 「 +-」 、小数点 「 . 」 、幂符号 「 eE」 。

状态定义：

​ 按照字符串从左到右的顺序，定义以下 9 种状态。

  1. 开始的空格

  2. 幂符号前的正负号

  3. 小数点前的数字

  4. 小数点、小数点后的数字

  5. 当小数点前为空格时，小数点、小数点后的数字

  6. 幂符号

  7. 幂符号后的正负号

  8. 幂符号后的数字

  9. 结尾的空格

Picture1.png

实现

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
private static class Solution {
    public boolean isNumber(String s) {
        Map[] states = {
            new HashMap<Character,Integer>() {{ put(' ', 0); put('s', 1); put('d', 2); put('.', 4); }}, // 0.
            new HashMap<Character,Integer>() {{ put('d', 2); put('.', 4); }},                           // 1.
            new HashMap<Character,Integer>() {{ put('d', 2); put('.', 3); put('e', 5); put(' ', 8); }}, // 2.
            new HashMap<Character,Integer>() {{ put('d', 3); put('e', 5); put(' ', 8); }},              // 3.
            new HashMap<Character,Integer>() {{ put('d', 3); }},                                        // 4.
            new HashMap<Character,Integer>() {{ put('s', 6); put('d', 7); }},                           // 5.
            new HashMap<Character,Integer>() {{ put('d', 7); }},                                        // 6.
            new HashMap<Character,Integer>() {{ put('d', 7); put(' ', 8); }},                           // 7.
            new HashMap<Character,Integer>() {{ put(' ', 8); }}                                         // 8.
        };
        int p = 0;
        char t;
        for (char c : s.toCharArray()) {
            if (c >= '0' && c <= '9') {
                t = 'd';
            } else if (c == '+' || c == '-') {
                t = 's';
            } else if (c == 'e' || c == 'E') {
                t = 'e';
            } else if (c == '.' || c == ' ') {
                t = c;
            } else {
                t = '?';
            }
            if (!states[p].containsKey(t)) {
                return false;
            }
            p = (int) states[p].get(t);
        }
        return p == 2 || p == 3 || p == 7 || p == 8;
    }
}