Not Only Algorithm,不仅仅是算法,关注数学、算法、数据结构、程序员笔试面试以及一切涉及计算机编程之美的内容 。。
你的位置:NoAlGo博客 » 题解 » 

LeetCode Valid Number 有限状态机

Leetcode algorithms 第 65 题:Valid Number。

题目

Validate if a given string is numeric.

Some examples:
“0″ => true
” 0.1 ” => true
“abc” => false
“1 a” => false
“2e10″ => true

Note: It is intended for the problem statement to be ambiguous. You should gather all requirements up front before implementing one.

解答

此题使用一般的判断非常繁琐,极其容易出错,但是可以使用有限状态机进行解决,思路较为直接,而且代码非常简短。

考虑所有可能的输入,不同的输入会导致状态的不同转移,把每种输入用一个数字进行表示如下:

  • 0:非法字符
  • 1:空格
  • 2:正负号
  • 3:小数点
  • 4:指数e
  • 5:数字

令状态S0为初始状态,考虑其在不同输入下的转移情况。

  • 0:数字带有非法字符,非法。转入非法状态,用状态-1表示。
  • 1:数字带有前导空格,合法。新状态和初始状态一样,转入状态0。
  • 2:数字带有正负号,合法。此时需要进入一个新的状态,用状态1表示(内容仅含正负号)。
  • 3:数字一开始即为小数点,合法,因为有如.1之类的数字。需要转入一个新的状态,用状态2表示(内容仅含小数点)。
  • 4:数字一开始即为指数e,非法。转入非法状态-1。
  • 5:数字一开始即为数字,合法。需要转入新状态,用状态3表示(内容仅含数字)。

为了方便,只需要考虑所有合法的转移即可,下面是状态0的含义及转移情况。状态0为初始状态,可以有空格。

  • 1->0:输入空格,转入自身。
  • 2->1:输入正负号,转入新状态1(仅含正负号)。
  • 3->2:输入小数点,转入新状态2(仅含小数点)。
  • 5->3:输入数字,转入新状态3(仅含数字)。

下面考虑状态1。状态1仅含有一个正负号,后面只允许接小数点或者数字。

  • 3->2:接小数点,新状态变为正负号+小数点,可以和状态2合并,转入新状态2([正负号] + 小数点)。
  • 5->3:接数字,新状态变为正负号+数字,可以和状态3合并,转入新状态3([正负号] + 数字)。

下面考虑状态2。状态2包含一个小数点,前面可能含有正负号,[正负号] + 小数点。此时后面只允许接数字。

  • 5->4:接数字,转入新状态4([正负号] + 小数点 + 数字)。

下面考虑状态3。状态3包含数字,前面可能有正负号,[正负号] + 数字。此时后面只允许接空格、小数点、指数e或者数字。

  • 1->4:接空格,转入新状态5(合法数字 + 空格)。
  • 3->4:接小数点,此时状态为数字加小数点,由于形如3.的数字也是合法数字,可以转入状态4([正负号] + 数字 + 小数点)。
  • 4->6:接指数e,转入新状态6,(不带e的合法数字 + e)。
  • 5->3:接数字,转入自身。

下面考虑状态4。状态4为[正负号] + 小数点 + 数字,或者[正负号] + 数字 + 小数点,本质上是一个合法的不带e的数字。其后面可以继续接数字,也可以接空格,指数e。

  • 1->5:接空格,转入状态5。
  • 4->6:接指数e,转入状态6。
  • 5->4:接数字,转入自身。

下面考虑状态5。状态5为一个合法数字接空格,为后导空格情况,此时只允许出现空格字符。

  • 1->5:接空格,转入自身。

下面考虑状态6。状态6为一个不带e的合法数字接e的情况,此时后面只允许出现正负号或者数字。

  • 2->7:接正负,转入新状态7(不带e的合法数字 + e + 正负号)。
  • 5->8:接数字,转入新状态8(不带e的合法数字 + e + 数字)。

下面考虑状态7。状态7为 不带e的合法数字 + e + 正负号,此时后面只允许接数字。

  • 5->8:接数字,转入状态8,状态8变为 不带e的合法数字 + e + [正负号] + 数字

下面考虑状态8:。状态8为 不带e的合法数字 + e + [正负号] + 数字,其后面只能够接数字,或者空格。

  • 1->5:接空格,转入状态5。
  • 5->8:接数字,转入自身。

此时,所有的状态已经考虑完毕,可以得到以下状态转换矩阵trans:

-1,  0,  1,  2, -1,  3
-1, -1, -1,  2, -1,  3
-1, -1, -1, -1, -1,  4
-1,  5, -1,  4,  6,  3
-1,  5, -1, -1,  6,  4
-1,  5, -1, -1, -1, -1
-1, -1,  7, -1, -1,  8
-1, -1, -1, -1, -1,  8
-1,  5, -1, -1, -1,  8

其中trans[i][j]即表示从状态i接受输入j进入的新状态。

还有最后一个问题,自动机中的哪些状态是合法的呢?根据合法数字的定义可以容易知道,状态3、4、5、8是合法状态。

现在可以轻松得到程序的代码了。

class Solution {
public:
    bool isNumber(const char *s) {
        enum InputType {
            INVALID, SPACE, SIGN, DOT, E, DIGIT, LEN
        };
        int trans[][LEN] = {
            {-1,  0,  1,  2, -1,  3},
            {-1, -1, -1,  2, -1,  3},
            {-1, -1, -1, -1, -1,  4},
            {-1,  5, -1,  4,  6,  3},
            {-1,  5, -1, -1,  6,  4},
            {-1,  5, -1, -1, -1, -1},
            {-1, -1,  7, -1, -1,  8},
            {-1, -1, -1, -1, -1,  8},
            {-1,  5, -1, -1, -1,  8}
        };
        int state = 0;
        while (*s) {
            InputType input;
            if (isspace(*s)) {
                input = SPACE;
            } else if (*s == '+' || *s == '-') {
                input = SIGN;
            } else if (*s == '.') {
                input = DOT;
            } else if (*s == 'e' || *s == 'E') {
                input = E;
            } else if (isdigit(*s)) {
                input = DIGIT;
            } else {
                input = INVALID;
            }
            state = trans[state][input];
            if (state == -1) {
                return false;
            }
            s++;
        }
        return state == 3 || state == 4 || state == 5 || state == 8;
    }
};
上一篇: 下一篇:

我的博客

NoAlGo头像编程这件小事牵扯到太多的知识,很容易知其然而不知其所以然,但真正了不起的程序员对自己程序的每一个字节都了如指掌,要立足基础理论,努力提升自我的专业修养。

站内搜索

最新评论