LeetCode Valid Number 有限状态机 >> NoAlGo博客

LeetCode Valid Number 有限状态机 » NoAlGo博客

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是合法状态。

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

Read full article from LeetCode Valid Number 有限状态机 » NoAlGo博客