概述

听名字就能大概猜出“有限状态自动机”是干嘛的了。

有一个当前状态 pre
每轮循环输入一个 cur
有限状态自动机可以根据事先的定义来进行状态的转移

有限状态自动机并不能降低算法的复杂度，但是可以让代码看起来非常简洁清爽，也不会写着写着就晕掉了。

例题

剑指 Offer 20. 表示数值的字符串

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

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

若干空格
一个小数或者整数
（可选）一个 'e' 或 'E' ，后面跟着一个整数
若干空格

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

（可选）一个符号字符（'+' 或 '-'）
下述格式之一：
1. 至少一位数字，后面跟着一个点 '.'
2. 至少一位数字，后面跟着一个点 '.'，后面再跟着至少一位数字
3. 一个点 '.' ，后面跟着至少一位数字

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

（可选）一个符号字符（’+’ 或 ‘-‘）
至少一位数字

部分数值列举如下：

["+100", "5e2", "-123", "3.1416", "-1E-16", "0123"]

部分非数值列举如下：

["12e", "1a3.14", "1.2.3", "+-5", "12e+5.4"]

示例 1：

1 2	输入：s = "0" 输出：true

示例 2：

1 2	输入：s = "e" 输出：false

示例 3：

1 2	输入：s = "." 输出：false

示例 4：

1 2	输入：s = " .1 " 输出：true

题解

先贴一段我第一次写时的代码，用的是暴力模拟，写半天自己都写晕了，到后面变量名字都开始乱七八糟了，因为不能一次性考虑到所有细节，所以根据WA给的测试用例缝缝补补勉强通过。

class Solution {
private:
    stringstream ss;
public:
    bool isNumber(string s) {
        ss << s;
        ss >> ws;
        if(ss.peek()=='+' || ss.peek()=='-') ss.get();
        bool hasnum=false;
        while(isdigit(ss.peek())){
            ss.get();
            hasnum=true;
        }
        if(ss.peek()=='.') {
            ss.get();
            bool hasnum2=false;
            while(isdigit(ss.peek())){
                ss.get();
                hasnum2=true;
            }
            if(!hasnum2 && !hasnum) return false;
        }
        else if(!hasnum) return false;

        if(ss.peek()=='e' || ss.peek()=='E'){
            ss.get();
            bool hasnum1=false;
            if(ss.peek()=='+' || ss.peek()=='-') ss.get();
            while(isdigit(ss.peek())){
                ss.get();
                hasnum1=true;
            }
            if(!hasnum1) return false;
        }
        ss >> ws;
        return ss.peek()==-1;
        
    }
};

而使用有限状态自动机就可以让代码非常清晰。我们可以定义如下的状态：

图源：LeetCode @Krahets 前辈的题解

在代码中，我们使用数组+字典来储存上图。只有退出后的状态为 2/3/7/8 中的一个时，我们才认为输入的字符串为合法的数值。

class Solution {
public:
    bool isNumber(string s) {
        stringstream ss;
        ss << s;
        vector<unordered_map<char, int>> states = {
            { {' ', 0},{ 's', 1},{ 'd', 2}, {'.', 4} },
            { {'d', 2},{ '.', 4} } ,
            { {'d', 2},{ '.', 3}, {'e', 5}, {' ', 8} },
            { {'d', 3}, {'e', 5}, {' ', 8} },
            { {'d', 3} },
            { {'s', 6}, {'d', 7} },
            { {'d', 7} },
            { {'d', 7}, {' ', 8} },
            { {' ', 8} }
        };
        int pre = 0;
        while (ss.peek() != -1) {
            char c = ss.get();
            char cur;
            if ('0' <= c && c <= '9') cur = 'd';
            else if (c == '+' || c == '-') cur = 's';
            else if (c == 'e' || c == 'E') cur = 'e';
            else if (c == '.' || c == ' ') cur = c;
            else cur = '?';
            if (states[pre].count(cur) <= 0) return false;
            pre = states[pre][cur];
        }
        return pre == 2 || pre == 3 || pre == 7 || pre == 8;
    }
};

有的没的

天才操作

13号回的学校。回校前精心挑选了一班快十几分钟的车次，然后当天到了宁波站了才发现终点站是杭州南，不是杭州东，少坐一站可不是快一点嘛。后来找乘务姐姐补了一站路。

新生要来报到了

明天新生就陆续要来报到了，我也该读大三了。没有人永远年轻，但永远有人年轻。

环己三烯的冬眠舱

有限状态自动机

概述

例题