[leetcode]Valid Number @ Python

原題位址：http://oj.leetcode.com/problems/valid-number/

題意：判斷輸入的字元串是否是合法的數。

解題思路：這題隻能用确定有窮狀态自動機(dfa)來寫會比較優雅。本文參考了http://blog.csdn.net/kenden23/article/details/18696083裡面的内容，在此緻謝！

首先這個題有9種狀态：

0初始無輸入或者隻有space的狀态

1輸入了數字之後的狀态

2前面無數字，隻輸入了dot的狀态

3輸入了符号狀态

4前面有數字和有dot的狀态

5‘e‘

or ‘e‘輸入後的狀态

6輸入e之後輸入sign的狀态

7輸入e後輸入數字的狀态

8前面有有效數輸入之後，輸入space的狀态

共9種狀态了，難設計的是6,7,8狀态。

分好之後就好辦了，設計出根據輸入進行狀态轉換就ok了。

這裡的輸入可以分：

invalid=0;#無效輸入包括: alphas, ‘(‘, ‘&‘ ans so on

space=1

sign=2 # ‘+‘

or ‘-‘

digit=3 # numbers

dot=4 # ‘.‘

exponent=5 # ‘e‘ or ‘e‘

轉移矩陣a(9x6)如下：

-1,  0,  3,  1,  2,  -1

-1,  8, -1,  1,

 4,   5

-1, -1, -1,  4, -1, -1

-1, -1, -1,  1, 2,

 -1

-1,  8, -1,  4, -1,  5

-1, -1,  6,  7,

-1, -1

-1, -1, -1,  7, -1, -1

-1,  8, -1,  7, -1, -1

-1,

 8, -1, -1, -1, -1

行代表了9種狀态，列代表了6種輸入方式也就是6種跳轉方式。舉個例子：a[0][2]=3，這有什麼含義呢？意思是：第0種狀态為【0初始無輸入或者隻有space的狀态】，在輸入第2種輸入【sign=2

# ‘+‘ or

‘-‘】後，會跳轉到第3種狀态【3輸入了符号狀态】。a[1][1]=8是什麼意思呢？意思是：第1種狀态為【1輸入了數字之後的狀态】，在輸入第1種輸入【space=1】後，跳轉到了第8種狀态【8前面有有效數輸入之後，輸入space的狀态】。

根據以上的解釋，大家應該明白什麼事狀态間的跳轉了，這個共9種狀态，是以是确定有窮自動機。其實難點在于狀态的分割，要把每種情況都想到。

而這9種狀态中：隻有1、4、7、8這四種狀态合法，是以最後state跳轉到這四種狀态之一時，說明輸入是合法的！

狀态轉移圖 from leetcode discuss：

代碼：