[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：

代码：