题目描述

验证给定的字符串是否可以解释为十进制数字.

示例:

"0" => true
" 0.1 " => true
"abc" => false
"1 a" => false
"2e10" => true
" -90e3   " => true
" 1e" => false
"e3" => false
" 6e-1" => true
" 99e2.5 " => false
"53.5e93" => true
" --6 " => false
"-+3" => false
"95a54e53" => false

数字: 0-9
小数点: .
符号: +, -
指数: e

解题思路

看过题解的同学应该发现了, 如果用Python, 很多人直接调用float函数, 如果转换成功则返回True, 如果抛出异常, 则返回False. 不得不说, 还真是个小机灵鬼呢~. 但是这种方式求解, 对于提升自己没什么太大的帮助. 下面讲一下如何用自动机理论去求解这道题, 已经忘了自动机为何物的同学先翻一下编译原理教材, 或者参考维基百科.

我们的目标是构造出一个DFA, 模拟输入字符串在DFA上的运行, 如果处理完输入的最后一个字符, DFA处在接受状态, 那么该字符串可以解释为十进制数, 否则不能. 但是很难直接构造出一个满足条件的DFA, 需要经过一个曲线救国的过程, 首先, 构造出一个能匹配目标字符串的正则表达式, 根据正则表达式构造出对应的NFA, 最后将NFA转换成等价的DFA, 有了这个DFA之后就可以构造出其对应的状态转换表, 并且在代码中使用了.

如何构造能够匹配十进制数的正则呢? 先说先我的思路, 一个十进制数可以划分成3个部分, 即: 1) 符号位; 2) base; 3) 幂次; 比如"-123.32e+4", 其中符号位和幂次可以为空, 并且这两部分的正则比较容易写. base部分有"23.", "23.34", "23", ".34"四种形式, 写一个匹配这4种形式的正则也比较容易, 各位看官可以自己实现一下, 各部分的正则写完之后拼接起来即可.

有了正则之后可以构造对应的NFA了, but how? 先看下正则表达式, 主要包含连接, 或, 闭包三种基本操作, 再复杂的正则也是由这三种基本操作组合而成的, 只需要了解这三种基本操作的NFA如何构造, 就可以构造出上面得到的正则对应的NFA了, 具体实现参考Thompson算法.

有了NFA之后, 需要构造等价的DFA, 所谓等价是二者接受的字符串集合相同, 因为NFA的状态转移不确定, 转成DFA之后方便模拟运行. 通常使用子集构造算法进行NFA到DFA的转换, 为了得到DFA的状态转换表, 这里根据之前计算出的NFA手动模拟了子集构造算法的运行, 得到的状态转换表如下:

其中状态2, 4, 5, 7, 8, 10是接受状态

代码实现

class Solution:

    table = [
        [1, 2, 3, -1, -1],
        [-1, 2, 3, -1, -1],
        [-1, 4, 5, 6, -1],
        [-1, 7, -1, -1, -1],
        [-1, 4, 8, 6, -1],
        [-1, 7, -1, 6, -1],
        [9, 10, -1, -1, -1],
        [-1, 7, -1, 6, -1],
        [-1, 8, -1, 6, -1],
        [-1, 10, -1, -1, -1],
        [-1, 10, -1, -1, -1]
    ]

    finals = [0, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1]

    def isNumber(self, s: str) -> bool:
        return Solution.dfa(s)

    @staticmethod
    def dfa(s: str) -> bool:
        s = s.strip()
        q = 0  # DFA的初始状态
        for ch in s:
            q = Solution.move(q, ch)
            # 跟踪状态转换
            # print("state: %d" % (q))
            if q == -1:
                return False
        return Solution.finals[q] == 1

    @staticmethod
    def move(q: int, ch):
        if ch in '+-':
            idx = 0
        elif ch in '0123456789':
            idx = 1
        elif ch in '.':
            idx = 2
        elif ch in 'e':
            idx = 3
        else:
            idx = 4
        return Solution.table[q][idx]

更多leetcode题解敬请期待。