JZ20 表示数值的字符串

发表于 分类于 本文字数： 676 阅读时长 ≈ 2 分钟

JZ20 表示数值的字符串

描述

请实现一个函数用来判断字符串str是否表示数值（包括科学计数法的数字，小数和整数）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
科学计数法的数字(按顺序）可以分成以下几个部分:
1.若干空格
2.一个整数或者小数
3.（可选）一个 'e' 或 'E' ，后面跟着一个整数(可正可负)
4.若干空格
         
小数（按顺序）可以分成以下几个部分：
1.若干空格
2.（可选）一个符号字符（'+' 或 '-'）
3. 可能是以下描述格式之一:
3.1 至少一位数字，后面跟着一个点 '.'
3.2 至少一位数字，后面跟着一个点 '.' ，后面再跟着至少一位数字
3.3 一个点 '.' ，后面跟着至少一位数字
4.若干空格

整数（按顺序）可以分成以下几个部分：
1.若干空格
2.（可选）一个符号字符（'+' 或 '-')
3. 至少一位数字
4.若干空格

例如，字符串[“+100”,”5e2”,”-123”,”3.1416”,”-1E-16”]都表示数值。
但是[“12e”,”1a3.14”,”1.2.3”,”+-5”,”12e+4.3”]都不是数值。

提示:

$1 <= str.length <= 25 \ str 仅含英文字母（大写和小写），数字（0-9），加号 ‘+’ ，减号 ‘-‘ ，空格 ‘ ‘ 或者点 ‘.’ \ 如果怀疑用例是不是能表示为数值的，可以使用python的print(float(str))去查看$

进阶：时间复杂度$O(n)$，空间复杂度$O(n)$

示例1

1
2
输入："123.45e+6"
返回值：true

示例2

1
2
输入："1.2.3"
返回值：false

示例3

1
2
输入："."
返回值：false

示例4

1
2
输入："    .2  "
返回值：true

题解

这道题其实和上一题差不多，纯模拟也可以做，但是这道题的官方题解给到了一个有限状态机(Finite State Machine)的解法，通过检查每个字符的状态，控制合法的状态转移以及合法的结束状态实现。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution:
    def isNumeric(self, str):
        # 定义状态转移表
        states = [
            {" ": 0, "s": 1, "d": 2, ".": 4},  # 0. 起始状态，处理前导空格
            {"d": 2, ".": 4},  # 1. 符号之后
            {"d": 2, ".": 3, "e": 5, " ": 8},  # 2. 小数点前的数字
            {"d": 3, "e": 5, " ": 8},  # 3. 小数点后的数字
            {"d": 3},  # 4. 只有小数点（前面没有数字）
            {"s": 6, "d": 7},  # 5. 指数e之后
            {"d": 7},  # 6. 指数符号之后
            {"d": 7, " ": 8},  # 7. 指数数字
            {" ": 8},  # 8. 后导空格
        ]

        p = 0  # 初始状态
        for c in str:
            if "0" <= c <= "9":
                t = "d"  # digit
            elif c in "+-":
                t = "s"  # sign
            elif c in "eE":
                t = "e"  # exponent
            elif c in ". ":
                t = c  # dot or space
            else:
                t = "?"  # unknown

            if t not in states[p]:
                return False
            p = states[p][t]

        # 可接受的结束状态：2(数字), 3(小数), 7(指数数字), 8(后导空格)
        return p in (2, 3, 7, 8)