这是 2020 年 9 月 2 日的每日一题。这道题本身并不难,但是让我明白了一个自动机的概念。直接来看题吧。

题目

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

我的思路

首先我们可以写出一个最复杂的数字:

+ 1 . 2 E + 6

我们把这个数字分成几个部分:

1 -> 开头符号
2 -> 整数部分
3 -> 小数点
4 -> 小数部分
5 -> 符号 E
6 -> 指数符号
7 -> 指数部分

然后我们就可以从左到右遍历一遍字符串,根据当前是第几个部分以及当前字符是什么来跳转到其他部分。

再到结尾的时候根据部分来判断是不是数字。

这里难点主要在于首尾空格以及类似 .2 这种格式数字的判断。

直接上代码:

  • 语言 :C++

这里我们用 now 这个变量来标志当前是什么部分,然后根据字符来区分。

class Solution {
public:
    bool isNumber(string s) {
        int index = 0;
        int now = 0;
        return isNumberD(s, index, now);
    }

    bool isNumberD(string &s, int index, int now){
        cout<<"index:"<<index<<" | now:"<<now<<endl;
        if(index == s.size()){
            now %= 8;
            return (now ==2 || now ==3 || now ==4 || now ==7);
        }

        if(s[index] == ' '){
            if(now == 0){
                return isNumberD(s, index+1, now);
            }else {
                return isNumberD(s, index+1, now+8);
            }
        }else{
            if(now > 7){
                return false;
            }
        }

        if(s[index] >= '0' && s[index] <= '9'){
            if(now < 2){
                return isNumberD(s, index+1, 2);
            }else if(now == 3){
                return isNumberD(s, index+1, 4);
            }else if(now == 5 || now == 6){
                return isNumberD(s, index+1, 7);
            }
            return isNumberD(s, index+1, now);
            
        }
        switch(s[index]){
            case '+':
            case '-':
                if(now == 0){
                    return isNumberD(s, index+1, 1);
                }else if(now == 5){
                    return isNumberD(s, index+1, 6);
                }else{
                    return false;
                }
                break;
            case '.':
                if(now < 3){
                    bool b = false;
                    if(index > 0 && s[index-1] >= '0' && s[index-1] <= '9'){
                        b = true;
                    }
                    if(index+1 < s.size() && s[index+1] >= '0' && s[index+1] <= '9'){
                        b = true;
                    }
                    if(!b){
                        return false;
                    }
                    return isNumberD(s, index+1, 3);
                }else{
                    return false;
                }
                break;
            case 'e':
            case 'E':
                if(now >= 2 && now <= 4){
                    return isNumberD(s, index+1, 5);
                }else{
                    return false;
                }
                break;
            default:
                return false;
        }

    }
};

自动机

看了官方题解,其实和我的思路大概是一样的,只不过它用了自动机这个概念。

自动机是一个计算模型。他有 状态 这样一个属性。 状态 可以是有限的也可以是无限的。其中一定有一个 初始状态 。然后这个模型可以接收参数。然后根据 参数 以及 当前状态 来确定 目标状态。然后切换状态。

对于一个自动机,最重要的就是 转移规则。一个 转移规则 一般包括 原状态 参数 以及 目标状态

对于这道题,状态是有限个的。所以我们可以使用有向图来表示一个自动机。其中点对应着 状态。边对应着 参数。边从 原状态 指向 目标状态
如下图:(图是力扣题解的)

jianzhi_20_fig1.png

实际上,我们的自动机还有一个 拒绝状态 ,表示当前状态对于参数没有 转移规则,此时判断字符不是数字。

上代码:

  • 语言:C++
class Solution {
public:
    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;
        }
    }

    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 typ = toCharType(s[i]);
            if (transfer[st].find(typ) == transfer[st].end()) {
                return false;
            } else {
                st = transfer[st][typ];
            }
        }
        return st == STATE_INTEGER || st == STATE_POINT || st == STATE_FRACTION || st == STATE_EXP_NUMBER || st == STATE_END;
    }
};

作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/biao-shi-shu-zhi-de-zi-fu-chuan-lcof/solution/biao-shi-shu-zhi-de-zi-fu-chuan-by-leetcode-soluti/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。