题目描述

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

数值（按顺序）可以分成以下几个部分：
若干空格
一个 小数 或者 整数
（可选）一个 ‘e’ 或 ‘E’ ，后面跟着一个 整数
若干空格

小数（按顺序）可以分成以下几个部分：
（可选）一个符号字符（’+’ 或 ‘-’）
下述格式之一：
至少一位数字，后面跟着一个点 ‘.’
至少一位数字，后面跟着一个点 ‘.’ ，后面再跟着至少一位数字
一个点 ‘.’ ，后面跟着至少一位数字

整数（按顺序）可以分成以下几个部分：
（可选）一个符号字符（’+’ 或 ‘-’）
至少一位数字

部分数值列举如下：
["+100", “5e2”, “-123”, “3.1416”, “-1E-16”, “0123”]

部分非数值列举如下：
[“12e”, “1a3.14”, “1.2.3”, “±5”, “12e+5.4”]

https://leetcode.cn/problems/biao-shi-shu-zhi-de-zi-fu-chuan-lcof

题解

遍历模拟

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
class Solution {
public:
    bool isNumber(string s) {
        // 去掉首尾空格
        int i = 0;
        while (i < s.size() && s[i] == ' ') ++i;
        s = s.substr(i);
        while (s.back() == ' ') s.pop_back();
        
        bool numFlag = false, eFlag = false, dotFLag = false;
        for (i = 0; i < s.size(); ++i) {
            // 如果是+-，必须在第一位或者紧跟在 e 后面
            if ((s[i] == '+' || s[i] == '-') && (i == 0 || s[i - 1] == 'e' || s[i - 1] == 'E')) {
                //;
            } else if(isdigit(s[i])) {
                numFlag = true;    // 如果是数字
            } else if ((s[i] == 'e' || s[i] == 'E') && !eFlag && numFlag) {
                // 如果是 e E，只能有一个 e E，前面必须是数字，而且后面也要求有数字
                eFlag = true, numFlag = false;
            } else if (s[i] == '.' && !dotFLag && !eFlag) {
                // 如果是 '.'，只能有一个 '.'，且前面不能是 e E
                dotFLag = true;
            } else {
                // 其他所有的非法情况
                return false;
            }
        }
        return numFlag;
    }
};

时间复杂度 O(n)，空间复杂度 O(1)

有限状态机

可以看官解说明，很容易理解，但是设各种状态，代码比较多。

来自官解

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
class Solution {
    enum State {
            STATE_INITIAL,
            STATE_INT_SIGN,
            STATE_INTEGER,
            STATE_POINT,
            STATE_POINT_WITHOUT_INT,
            STATE_FRACTION,
            STATE_EXP,
            STATE_EXP_SIGN,
            STATE_EXP_NUMBER,
            STATE_END
        };

        enum CharType {
            CHAR_NUMBER,
            CHAR_EXP,
            CHAR_POINT,
            CHAR_SIGN,
            CHAR_SPACE,
            CHAR_ILLEGAL
        };

        CharType toCharType(char ch) {
            if (ch >= '0' && ch <= '9')
                return CHAR_NUMBER;
            else if (ch == 'e' || ch == 'E')
                return CHAR_EXP;
            else if (ch == '.')
                return CHAR_POINT;
            else if (ch == '+' || ch == '-')
                return CHAR_SIGN;
            else if (ch == ' ')
                return CHAR_SPACE;
            else 
                return CHAR_ILLEGAL;
        }
public:
    bool isNumber(string s) {
        unordered_map<State, unordered_map<CharType, State>> transfer {
            {STATE_INITIAL, {
                {CHAR_SPACE, STATE_INITIAL},
                {CHAR_NUMBER, STATE_INTEGER},
                {CHAR_POINT, STATE_POINT_WITHOUT_INT},
                {CHAR_SIGN, STATE_INT_SIGN}
            }},
            {STATE_INT_SIGN, {
                {CHAR_NUMBER, STATE_INTEGER},
                {CHAR_POINT, STATE_POINT_WITHOUT_INT}
            }},
            {STATE_INTEGER, {
                {CHAR_NUMBER, STATE_INTEGER},
                {CHAR_EXP, STATE_EXP},
                {CHAR_POINT, STATE_POINT},
                {CHAR_SPACE, STATE_END}
            }},
            {STATE_POINT, {
                {CHAR_NUMBER, STATE_FRACTION},
                {CHAR_EXP, STATE_EXP},
                {CHAR_SPACE, STATE_END}
            }},
            {STATE_POINT_WITHOUT_INT, {
                {CHAR_NUMBER, STATE_FRACTION}
            }},
            {STATE_FRACTION, {
                {CHAR_NUMBER, STATE_FRACTION},
                {CHAR_EXP, STATE_EXP},
                {CHAR_SPACE, STATE_END}
            }},
            {STATE_EXP, {
                {CHAR_NUMBER, STATE_EXP_NUMBER},
                {CHAR_SIGN, STATE_EXP_SIGN}
            }},
            {STATE_EXP_SIGN, {
                {CHAR_NUMBER, STATE_EXP_NUMBER}
            }},
            {STATE_EXP_NUMBER, {
                {CHAR_NUMBER, STATE_EXP_NUMBER},
                {CHAR_SPACE, STATE_END}
            }},
            {STATE_END, {
                {CHAR_SPACE, STATE_END}
            }}
        };

        int len = s.length();
        State st = STATE_INITIAL;
        for (int i = 0; i < len; ++i) {
            CharType chtype = toCharType(s[i]);
            if (transfer[st].find(chtype) == transfer[st].end()) {
                return false;
            } else {
                st = transfer[st][chtype];
            }
        }
        return 
        st == STATE_INTEGER || 
        st == STATE_POINT ||
        st == STATE_FRACTION || 
        st == STATE_EXP_NUMBER ||
        st == STATE_END;
    }
};

时间复杂度 O(n)，空间复杂度 O(1)