表示数值的字符串

题目描述

请实现一个函数用来判断字符串是否表示数值(包括整数和小数)。例如,字符串"+100"、"5e2"、"-123"、"3.1416"、"0123"都表示数值,但"12e"、"1a3.14"、"1.2.3"、"+-5"、"-1E-16"及"12e+5.4"都不是。

解题技巧

• 方法1：有限状态自动机

字符类型:空格「 」、数字「0—9」、正负号「+-」、小数点「.」、幂符号「e」 。

状态定义:按照字符串从左到右的顺序,定义以下 9 种状态。

1. 开始的空格
2. 幂符号前的正负号
3. 小数点前的数字
4. 小数点、小数点后的数字
5. 当小数点前为空格时,小数点、小数点后的数字
6. 幂符号
7. 幂符号后的正负号
8. 幂符号后的数字
9. 结尾的空格

结束状态:合法的结束状态有2,3,7,8。

算法流程:

1. 初始化:

1. 状态转移表states:设states[i],其中i为所处状态,states[i]使用哈希表存储可转移至的状态。键值对(key, value)含义:若输入key,则可从状态i转移至状态value。
2. 当前状态p:起始状态初始化为p=0。

2. 状态转移循环:遍历字符串s的每个字符c

1. 记录字符类型t:分为四种情况。
2. 当c为正负号时,执行t='s';
3. 当c为数字时,执行t='d';
4. 当c为.,e,E,空格时,执行t=c(即用字符本身表示字符类型);
5. 否则,执行t='?',代表为不属于判断范围的非法字符,后续直接返回false。
6. 终止条件:若字符类型t不在哈希表states[p]中,说明无法转移至下一状态,因此直接返回False。
7. 状态转移:状态p转移至states[p][t]。

3. 返回值:跳出循环后,若状态$p \in {2, 3, 7, 8}$,说明结尾合法,返回True,否则返回False。

复杂度分析:

时间复杂度$O(N)$:其中N为字符串s的长度,判断需遍历字符串,每轮状态转移的使用$O(1)$时间。

空间复杂度$O(1)$:states和p使用常数大小的额外空间。

class Solution:
    def isNumber(self, s: str) -> bool:
        states = [
            { ' ': 0, 's': 1, 'd': 2, '.': 4 }, # 0. start with 'blank'
            { 'd': 2, '.': 4 } ,                # 1. 'sign' before 'e'
            { 'd': 2, '.': 3, 'e': 5, ' ': 8 }, # 2. 'digit' before 'dot'
            { 'd': 3, 'e': 5, ' ': 8 },         # 3. 'digit' after 'dot'
            { 'd': 3 },                         # 4. 'digit' after 'dot' (‘blank’ before 'dot')
            { 's': 6, 'd': 7 },                 # 5. 'e'
            { 'd': 7 },                         # 6. 'sign' after 'e'
            { 'd': 7, ' ': 8 },                 # 7. 'digit' after 'e'
            { ' ': 8 }                          # 8. end with 'blank'
        ]
        p = 0                           # start with state 0
        for c in s:
            if '0' <= c <= '9': t = 'd' # digit
            elif c in "+-": t = 's'     # sign
            elif c in ".eE ": t = c     # dot, e, blank
            else: t = '?'               # unknown
            if t not in states[p]: return False
            p = states[p][t]
        return p in (2, 3, 7, 8)