《剑指offer》 20.表示数值的字符串

剑指offer
留言

note:这道题两种解法：确定有限状态自动机、if-else硬判断。前者状态机我认为是CS学生应该掌握的一种能力（编译原理中有用到），但是效率可能会有点慢。后者需要比较清晰的思维进行判断，当然基于状态机似乎也可以更好写一点。Ps.一鸽鸽一周，不愧是我！

题目描述

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

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

  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”]

方法一：确定有限状态自动机（DFA）

思路

确定有限状态自动机是一种计算模型，对于虽然没学过编译原理，但是学过一点点形式化知识（模型检测）的我来说，是进行形式化建模分析验证的必备知识。确定有限状态自动机是一个能够实现状态转移的自动机，对于给定的属于该自动机的状态和一个属于自动机字母表$\Sigma$。它可以根据事先给定的转移函数转移到下个状态。自动机$\mathcal{A}$表述为五元组是：

其中：

  • $Q$是一个非空有限状态的集合

  • $\Sigma$是一个非空有限字符的集合

  • $\delta$是一个单值映射的转移函数
  • $s$是一个开始状态，$s\in Q$
  • $F$是一个接受状态集合，$F\subseteq Q$

稍微复习了自动机的知识之后，我们大概知道了自动机其实就是最重要的就是两大部分，状态和迁移，其中状态又分为开始状态、接受状态（终结状态）和其他状态，转移关系由转移字符和转移函数决定。

对于这道题，我们就要分析它都有那些状态，转移关系又是如何的：

初步分析状态可能有以下几种：

  • 起始开头的空格
  • 数字的符号位
  • 数字的整数部分
  • 小数点（左边有整数）
  • 小数点（左边无整数）
  • 小数部分
  • 指数符号e\E
  • 指数部分的符号位
  • 指数部分的数字部分
  • 最后结束的空格

这里需要注意的是，上述状态中虽然有些状态内容是相同的，比如小数点（左边有整数）和小数点（左边无整数）、数字的整数部分和小数部分和指数部分的数字部分、开头和结尾的空格。但是他们依然属于不同的状态，这是因为他们的前驱状态与后继状态是完全不同的，甚至某些本身就有普通状态和接收状态的区分。所以一定要以不同的状态来看待，个人认为如何区分也是找出状态机较为复杂的一点。

接收状态也就是状态机的停止状态，分析我们可以得到5个接收状态：整数部分、小数点（左有整数部分）、小数部分、指数部分和结束状态。

总之经过对题目分析，我们可以得到最后的DFA如下图所示：确定有限状态机.png

我们的转移条件抽象为了五种元素——空格、正负号、数字、小数点和指数标志E\e

代码

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
class Solution {
    enum State{
        STATE_INITIAL,
        STATE_SIGNAL,
        STATE_INTEGER,
        STATE_DOTPOINT,
        STATE_FRACTION,
        STATE_DOTPOINT_LEFTNONUM,
        STATE_EXP,
        STATE_EXPSIGNAL,
        STATE_EXPINTEGER,
        STATE_FINISH
    };

    enum Guard{
        GUARD_SPACE,
        GUARD_NUM,
        GUARD_DOT,
        GUARD_E,
        GUARD_SIG,
        GUARD_ILLIGAL
    };

    Guard toGuard(char c){
        if(c=='+' || c=='-')
            return GUARD_SIG;
        if(c==' ')
            return GUARD_SPACE;
        if(c=='.')
            return GUARD_DOT;
        if(c=='e' || c=='E')
            return GUARD_E;
        if(c<='9' && c>='0')
            return GUARD_NUM;
        else
            return GUARD_ILLIGAL;
    }
public:
    bool isNumber(string s) {
        unordered_map<State,unordered_map<Guard,State>> trans{
            {
                STATE_INITIAL,{
                    {GUARD_SPACE,STATE_INITIAL},
                    {GUARD_NUM,STATE_INTEGER},
                    {GUARD_DOT,STATE_DOTPOINT_LEFTNONUM},
                    {GUARD_SIG,STATE_SIGNAL}
                }
            },{
                STATE_SIGNAL,{
                    {GUARD_NUM,STATE_INTEGER},
                    {GUARD_DOT,STATE_DOTPOINT_LEFTNONUM}
                }
            },{
                STATE_INTEGER,{
                    {GUARD_E,STATE_EXP},
                    {GUARD_DOT,STATE_DOTPOINT},
                    {GUARD_NUM,STATE_INTEGER},
                    {GUARD_SPACE,STATE_FINISH}
                }
            },{
                STATE_DOTPOINT,{
                    {GUARD_E,STATE_EXP},
                    {GUARD_NUM,STATE_FRACTION},
                    {GUARD_SPACE,STATE_FINISH}
                }
            },{
                STATE_DOTPOINT_LEFTNONUM,{
                    {GUARD_NUM,STATE_FRACTION}
                }
            },{
                STATE_FRACTION,{
                    {GUARD_NUM,STATE_FRACTION},
                    {GUARD_E,STATE_EXP},
                    {GUARD_SPACE,STATE_FINISH}
                }
            },{
                STATE_EXP,{
                    {GUARD_SIG,STATE_EXPSIGNAL},
                    {GUARD_NUM,STATE_EXPINTEGER}
                }
            },{
                STATE_EXPSIGNAL,{
                    {GUARD_NUM,STATE_EXPINTEGER}
                }
            },{
                STATE_EXPINTEGER,{
                    {GUARD_NUM,STATE_EXPINTEGER},
                    {GUARD_SPACE,STATE_FRACTION}
                }
            },{
                STATE_FINISH,{
                    {GUARD_SPACE,STATE_FINISH}
                }
            }
        };

        State state = STATE_INITIAL;

        for(auto c:s){
            Guard guard = toGuard(c);
            if(trans[state].find(guard)==trans[state].end())
                return false;
            state = trans[state][guard];
        }

        return state==STATE_INTEGER || state==STATE_DOTPOINT || state==STATE_FRACTION || state==STATE_EXPINTEGER || state==STATE_FINISH;
    }
};

友情提示：在使用enum类型时，最好将state和guard进行区分，不然容易弄混。

复杂度分析

  • 时间复杂度:$O(n)$。n为字符串长度
  • 空间复杂度$O(1)$。我们只需要常数级别的状态转移表。

方法二：if-else分析解法

思路

很容易想到也很容易出错的一个想法，由于数字有四种元素组成，所以我们用四个变量来判断前面是否出现过数字、正负号、E/e以及小数点。去除掉前面的空格后，我们就可以对剩下的字符进行遍历，由于数字中间不能出现空格， 所以一但出现空格我们就可以跳出遍历，然后对剩下遍历，只需要看是否全是空格，不是则返回false。

难度就在中间如何进行循环遍历了：

如开头分析，数字由0-9整数、正负号、E/e和小数点组成，那中间的循环遍历我们需要做的就是判断每一个字符属于那种元素，而这种元素出现在这个位置是否合法。接下来逐个分析四种元素的合法出现前提：

  • 0-9的数字：显然0-9的数字是可以连续重复并独自出现的，连续重复意味着我们可以用while循环直接遍历，直到不是数字或者到了字符串尽头；独自说明它不要求有什么前置条件。所以当这种元素出现时，我们不用在乎之前出现的字符如何，只需要在这种元素出现之后，将出现过数字的标志置为true，因为它可能会影响其他元素的合法性
  • 正负号：正负号合法出现的位置有两个，一是在整数部分的最前面（也就是0-9数字、小数点、正负号、e/E都没出现过），二是在指数部分最前面，但是它不能出现在整数部分或者小数部分之后。那么这里就是有一个冲突就是如果正负号没有出现在整数部分的最前面，而是出现在了指数部分最前面，那么它前面的整数和小数点一定出现过了。这时就需要我们分析其他条件——e/E的存在。
  • e/E：e/E作为指数部分出现的前兆与底数部分的结束，必须要求前面一定至少出现过整数部分，并且一定不能出现过自身。也就是0-9的数字的标志不能是false以及e/E的标志一定不能是true。而在出现之后，我们肯定要将e/E的标志置为true。同时我们回过头考虑正负号的问题，如果我们在e/E出现之后，重置0-9数字标志、小数点标志以及正负号标志为false，就可以将正负号的第二种可能归并到第一种位置。
  • 小数点：小数点出现的位置要求两点，第一是之前没有出现过小数点，二是之前没出现过e/E。所以要求这两个标志不能为true。

虽然到这里已经分析完了四种元素，但其实不排除输入中还有一些空格，面对这种情况，我们可以遇到空格直接跳出遍历。空格只有两种可能，一种是后面的全是空格，另一种是后面还有其他成分。那我们就可以直接单独遍历剩下元素，直到不是空格，然后判断是否到达了字符串末尾，来看是否符合要求。

最后还有一个特殊情况就是我们不允许整个字符串中没有出现一个0-9数字，所以我们在最后需要判断一下，数字是否曾经出现过。

代码

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
class Solution {
public:
    bool isNumber(string s) {
        int n = s.size();
        bool hasNum = false, hasE = false, hasSign = false, hasDot = false;
        int i = 0;
        /* 去除前导空格 */
        while(s[i]==' ' && i<n){
            i++;
        }
        if(i==n)
            return false;
        while (i < n) {
            while(s[i]>='0' && s[i]<='9' && i<n){
                hasNum = true;
                i++;
            }
            if(i==n)
                break;
            if(s[i]=='e' || s[i]=='E'){
                if(hasE || !hasNum){
                    return false;
                }
                hasE=true;
                hasDot=true;
                hasSign=false;
                hasNum=false;
            } else if(s[i]=='+' || s[i]=='-'){
                if(hasSign||hasNum||hasDot)
                    return false;
                hasSign=true;
            } else if(s[i]=='.'){
                if(hasDot || hasE)
                    return false;
                hasDot = true;
            }else if(s[i]==' ')
                break;
            else
                return false;
            i++;
        }
        while(i<n && s[i]==' ')
            i++;
        return i==n && hasNum;
    }

};

复杂度分析

  • 时间复杂度$O(n)$。遍历完了整个字符串
  • 空间复杂度$O(1)$。除了四个标志变量，没有使用额外空间。