【题解】剑指Offer-20 表示数值的字符串

发表于 分类于 ， ， 本文字数： 179 阅读时长 ≈ 1 分钟
剑指Offer-20 表示数值的字符串 类型 字符串 自动机

表示数值的字符串(剑指Offer-20)

题面

请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串"+100"、"5e2"、"-123"、"3.1416"、"-1E-16"、"0123"都表示数值，但"12e"、"1a3.14"、"1.2.3"、"+-5"及"12e+5.4"都不是。

思路

自动机。

状态转移

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

代码

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
class Solution {
public:
    bool isNumber(string s) {
        unordered_map<char, int> mp[9];
        mp[0][' ']=0; mp[0]['s']=1; mp[0]['d']=2; mp[0]['.']=4;
        mp[1]['d']=2; mp[1]['.']=4;
        mp[2]['d']=2; mp[2]['.']=3; mp[2]['e']=5; mp[2][' ']=8;
        mp[3]['d']=3; mp[3]['e']=5; mp[3][' ']=8;
        mp[4]['d']=3;
        mp[5]['s']=6; mp[5]['d']=7;
        mp[6]['d']=7;
        mp[7]['d']=7; mp[7][' ']=8;
        mp[8][' ']=8;

        int p = 0;
        char t;
        for(char c:s){
            if('0'<=c && c<='9') t = 'd';
            else if(c=='+' || c=='-') t = 's';
            else if(c=='e' || c=='E') t = 'e';
            else t = c;

            if(mp[p].find(t) == mp[p].end()) return false;
            p = mp[p][t];
        }
        return (p==2 || p==3 || p==7 || p==8);
    }
};