[Leetcode][python]Valid Number

拼搏现实的明天。 2022-06-07 07:14 144阅读 0赞

## 题目大意 ##

判断一个字符串是否是数值类型

## 解题思路 ##

该题差评无数，但绝对是一个好题目。最优雅的解法是**有限状态机**，我的脑海中浮现了以前上课时候学的有限状态机知识，所以这题其实思路一目了然！  
参考：  
[http://www.cnblogs.com/zuoyuan/p/3703075.html][http_www.cnblogs.com_zuoyuan_p_3703075.html]

首先这个题有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’

行代表了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的状态】。

![这里写图片描述][012016243309923.png]

## 代码 ##

class Solution(object):
        def isNumber(self, s):
            """
            :type s: str
            :rtype: bool
            """
            INVALID=0; SPACE=1; SIGN=2; DIGIT=3; DOT=4; EXPONENT=5;
            #0invalid,1space,2sign,3digit,4dot,5exponent,6num_inputs
            transitionTable=[[-1,  0,  3,  1,  2, -1],    #0 no input or just spaces 
                             [-1,  8, -1,  1,  4,  5],    #1 input is digits 
                             [-1, -1, -1,  4, -1, -1],    #2 no digits in front just Dot 
                             [-1, -1, -1,  1,  2, -1],    #3 sign 
                             [-1,  8, -1,  4, -1,  5],    #4 digits and dot in front 
                             [-1, -1,  6,  7, -1, -1],    #5 input 'e' or 'E' 
                             [-1, -1, -1,  7, -1, -1],    #6 after 'e' input sign 
                             [-1,  8, -1,  7, -1, -1],    #7 after 'e' input digits 
                             [-1,  8, -1, -1, -1, -1]]    #8 after valid input input space
            state=0; i=0
            while i<len(s):
                inputtype = INVALID
                if s[i]==' ': inputtype=SPACE
                elif s[i]=='-' or s[i]=='+': inputtype=SIGN
                elif s[i] in '0123456789': inputtype=DIGIT
                elif s[i]=='.': inputtype=DOT
                elif s[i]=='e' or s[i]=='E': inputtype=EXPONENT
    
                state=transitionTable[state][inputtype]
                if state==-1: return False
                else: i+=1
            return state == 1 or state == 4 or state == 7 or state == 8

## 总结 ##

感慨下，我认为公司笔试题很有可能会有这种有限状态机知识的题目，毕竟可以考察好几门学科知识～

[http_www.cnblogs.com_zuoyuan_p_3703075.html]: http://www.cnblogs.com/zuoyuan/p/3703075.html
[012016243309923.png]: /images/20220607/4423969c9ac34256ae61c2d8989f8677.png