表示数值的字符串

发表于 更新于
本文字数： 4.7k 阅读时长 ≈ 4 分钟

LeetCode每日一题，剑指 Offer 20. 表示数值的字符串

先看题目描述

大意就是让我们判断一个字符串是否是表示数值，里面会有小数点和 e 等

算法和思路

这题一开始自己写的各种案例都过不去，就看题解，看题解觉得别人的思路比较好

本题使用有限状态自动机。根据字符类型和合法数值的特点，先定义状态，再画出状态转移图，最后编写代码即可。

字符类型：

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

状态定义：

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

  1. 开始的空格

  2. 幂符号前的正负号

  3. 小数点前的数字

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

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

  6. 幂符号

  7. 幂符号后的正负号

  8. 幂符号后的数字

  9. 结尾的空格

结束状态：

合法的结束状态有 2, 3, 7, 8 。

算法流程：

  1. 初始化：
    1. 状态转移表 states ： 设 states[i]，其中 i 为所处状态， states[i] 使用哈希表存储可转移至的状态。键值对 (key, value) 含义：若输入 key ，则可从状态 i 转移至状态 value
    2. 当前状态 p ： 起始状态初始化为 p = 0
  2. 状态转移循环： 遍历字符串 s 的每个字符 c
    1. 记录字符类型 t ： 分为四种情况。
      • 当 c 为正负号时，执行 t = ‘s’ ;
      • 当 c 为数字时，执行 t = ‘d’ ;
      • 当 c 为 e , E 时，执行 t = ‘e’ ;
      • 当 c 为 . , 空格 时，执行 t = c （即用字符本身表示字符类型）;
        否则，执行 t = ‘?’ ，代表为不属于判断范围的非法字符，后续直接返回 False。
    2. 终止条件： 若字符类型 tt 不在哈希表 states[p]states[p] 中，说明无法转移至下一状态，因此直接返回 False
    3. 状态转移： 状态 p 转移至 states[p]
  3. 返回值： 跳出循环后，若状态 p ∈ 2,3,7,8 ，说明结尾合法，返回 True，否则返回 False

算法源码

这是看题解里的源码

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
class Solution {
    public boolean isNumber(String s) {
        Map[] states = {
            new HashMap<>() {{ put(' ', 0); put('s', 1); put('d', 2); put('.', 4); }}, // 0.
            new HashMap<>() {{ put('d', 2); put('.', 4); }},                           // 1.
            new HashMap<>() {{ put('d', 2); put('.', 3); put('e', 5); put(' ', 8); }}, // 2.
            new HashMap<>() {{ put('d', 3); put('e', 5); put(' ', 8); }},              // 3.
            new HashMap<>() {{ put('d', 3); }},                                        // 4.
            new HashMap<>() {{ put('s', 6); put('d', 7); }},                           // 5.
            new HashMap<>() {{ put('d', 7); }},                                        // 6.
            new HashMap<>() {{ put('d', 7); put(' ', 8); }},                           // 7.
            new HashMap<>() {{ 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;
    }
}

下面这个是自己实现的，是一直提交，一直试错来找到少考虑的情况，然后添加 if 语句最后成功的，感觉方法略蠢

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
class Solution {
    public boolean isNumber(String s) {
        int j = s.length() - 1;
        int i = 0;
        if (j == -1) return false;
        while (j >= 0 && s.charAt(j) == ' ') j--;
        while (i < s.length() && s.charAt(i)  == ' ') i++;
        if (i == s.length()) return false;
        return isNumber2(s.substring(i, j + 1));
    }

    public boolean isNumber2(String s) {
        int len = s.length();
        if (len == 0) return false;
        int index = 0;
        while (index < len && !Character.isDigit(s.charAt(index))) index++;
        if (index == len) return false;
        if (!Character.isDigit(s.charAt(0))&& (s.charAt(1) == 'e' || s.charAt(1) == 'E')) return false;
        if (s.charAt(0) == '.') return aftedDot(s.substring(1, len));
        if (s.charAt(0) != '+' && s.charAt(0) != '-' && !Character.isDigit(s.charAt(0))) return false;
        for (int i = 1; i < len; i++) {
            if(s.charAt(i) == 'e' || s.charAt(i) == 'E') return afterE(s.substring(i + 1, len));
            if (s.charAt(i) == '.') return aftedDot(s.substring(i + 1, len));
            if (!Character.isDigit(s.charAt(i))) return false;
        }
        return true;
    }

    public boolean afterE(String s) {
        int len = s.length();
        if (len == 1 && !Character.isDigit(s.charAt(0))) return false;
        if (len == 0 || s.charAt(0) != '-' && s.charAt(0) != '+' && !Character.isDigit(s.charAt(0))) return false;
        for (int i = 1; i < len; i++) {
            if (!Character.isDigit(s.charAt(i))) return false;
        }
        return true;
    }

    public boolean aftedDot(String s) {
        int len = s.length();
        if (len == 0) return true;
        for (int i = 0; i < len; i++) {
            if (s.charAt(i) == 'e' || s.charAt(i) == 'E') return afterE(s.substring(i + 1, len));
            if (!Character.isDigit(s.charAt(i))) return false;
        }
        return true;
    }
}