LeetCode第六十五题

自己代码的开源仓库:click here 欢迎Star和Fork :)

题目描述

有效数字（按顺序）可以分成以下几个部分：

一个小数或者整数
（可选）一个 ‘e’ 或 ‘E’ ，后面跟着一个整数
小数（按顺序）可以分成以下几个部分：

（可选）一个符号字符（’+’ 或 ‘-‘）
下述格式之一：
至少一位数字，后面跟着一个点 ‘.’
至少一位数字，后面跟着一个点 ‘.’ ，后面再跟着至少一位数字
一个点 ‘.’ ，后面跟着至少一位数字
整数（按顺序）可以分成以下几个部分：

（可选）一个符号字符（’+’ 或 ‘-‘）
至少一位数字

部分有效数字列举如下：
[“2”, “0089”, “-0.1”, “+3.14”, “4.”, “-.9”, “2e10”, “-90E3”, “3e+7”, “+6e-1”, “53.5e93”, “-123.456e789”]

部分无效数字列举如下：
[“abc”, “1a”, “1e”, “e3”, “99e2.5”, “—6”, “-+3”, “95a54e53”]

给你一个字符串 s ，如果 s 是一个有效数字，请返回 true 。


示例 1：

输入：s = "0"
输出：true
示例 2：

输入：s = "e"
输出：false
示例 3：

输入：s = "."
输出：false
示例 4：

输入：s = ".1"
输出：true
 

提示：

1 <= s.length <= 20
s 仅含英文字母（大写和小写），数字（0-9），加号 '+' ，减号 '-' ，或者点 '.' 。

解法

遍历原理已经忘记多时了。这里参考了一下大佬的题解，写成的。

首先看到题目是可以想到使用自动机的，因此需要画出状态转移图，然后再根据状态转移图来写出状态转移表，最后通过一个个字符串对应的状态进行查表来得到最终状态。

所有的状态为：
所有状态：

0. 初始状态
1.符号位
2.整数部分
3.左侧有整数的小数点
4.左侧无整数的小数点(根据前面的第二条额外规则，需要对左侧有无整数的两种小数点做区分)
5.小数部分
6.字符 e/E
7.指数部分的符号位
8.指数部分的整数部分

其中2、3、5、8为终止状态(可以接受)，还定义一个-1作为不可接收状态，直接结束。

状态转移图：

figure.1

状态转移表：

sate	blank	+/-	0-9	.	e	other
0	0	1	6	2	-1	-1
1	-1	-1	6	2	-1	-1
2	-1	-1	3	-1	-1	-1
3	8	-1	3	-1	4	-1
4	-1	7	5	-1	-1	-1
5	8	-1	5	-1	-1	-1
6	8	-1	6	3	4	-1
7	-1	-1	5	-1	-1	-1
8	8	-1	-1	-1	-1	-1

代码

class Solution(object):
    # 确定下一个状态
    def make(self,c):
        if c == ' ':
            return 0
        elif c == '+':
            return 1
        elif c == '-':
            return 1
        elif c == '.':
            return 3
        elif c == 'e' or c == 'E':
            return 4
        else:
            # 数字情况
            if c >= '0' and c <= '9':
                return 2
            # 其他情况
            else:
                return 5
    def isNumber(self, s):
        """
        :type s: str
        :rtype: bool

        核心思想：
                使用DFA求解
                分析题意、画出状态转移图(可以不是最简的)
                根据状态转移图写出状态转移表
                状态共8个状态，下标为0、1、2、3、4、5、6、7、8
        """
        state = 0 # 状态
        finals = [0,0,0,1,0,1,1,0,1]  # 最终可接受的状态 1表示可以介绍 0表示不可以接收
        # 状态转移表
        transfer = [[ 0, 1, 6, 2,-1,-1],
                    [-1,-1, 6, 2,-1,-1],
                    [-1,-1, 3,-1,-1,-1],
                    [ 8,-1, 3,-1, 4,-1],
                    [-1, 7, 5,-1,-1,-1],
                    [ 8,-1, 5,-1,-1,-1],
                    [ 8,-1, 6, 3, 4,-1],
                    [-1,-1, 5,-1,-1,-1],
                    [ 8,-1,-1,-1,-1,-1]]

        for i in range(len(s)):
            state = transfer[state][self.make(s[i])] # 访问状态转移表转移到下一个状态
            if state < 0: # 状态达到不可接受状态
                return False

        return bool(finals[state])

if __name__ == '__main__':
    s = Solution()
    print(s.isNumber('95a54e53'))