LeetCode 65. 有效数字（难）& 剑指offer 面试题20. 表示数值的字符串（中）

基于编译原理的有限状态机思想和正则匹配都可以解这道题，如果要用《剑指offer》的方法解是无法通过LeetCode设计的那些杂七杂八的特殊测试样例的。常规解法解这个题，就是在没事找事做！

题目

验证给定的字符串是否可以解释为十进制数字。
说明: 我们有意将问题陈述地比较模糊。在实现代码之前，你应当事先思考所有可能的情况。这里给出一份可能存在于有效十进制数字中的字符列表：
数字 0-9
指数 - "e"
正/负号 - "+"/"-"
小数点 - "."
当然，在输入中，这些字符的上下文也很重要。

测试用例

  • 功能测试（正数或者负数；包含或者不包含整数部分的数值；包含或者不包含小数部分的数值；包含或者不包含指数部分的数值；各种不能表达有效数值的字符串）。
  • 特殊测试（输入字符串和模式字符串是 nullptr、空字符串）。

考点

考查应聘者对字符串的编程能力。 考查应聘者分析问题的能力。面试官希望应聘者能够从不同类型的数值中分析出规律。 考查应聘者思维的全面性。应聘者要全面考虑数值整数、小数、指数部分的特点，比如哪些部分可以出现正负号，而哪些部分不能出现。在应聘者写完代码之后，面试官会期待应聘者能够完备地测试用例来验证自己的代码。

示例

例如: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
"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

考察知识点

字符串、基于编译原理的有限状态机

核心思想

直接判断

剑指offer的思路 可以把符合要求的数字归纳为 A[.[B]][e|E C] 的模式 A是整数部分，非必须，是以+/-开头的 '0' 到 '9' 的字符串。 B是小数部分，是无符号的 '0' 到 '9' 的字符串。 C是指数部分，是以+/-开头的 '0' 到 '9' 的字符串。 按照上述思路，按照整数部分、小数部分、指数部分依次处理即可。

LeetCode设置测的特殊测试样例很多，如果按照剑指offer上的做法写，通过不了，还是要做很多修改，详见代码中的测试部分和逻辑部分，添加了很多特判。

限状态机

思想
从 0 开始总共有 9 个状态，橙色代表可接受状态，也就是表示此时是合法数字，橙色代表终止状态。总共有四大类输入，数字，小数点，e 和 正负号。DFA 从状态 0 接受串 s 作为输入。当s耗尽的时候如果当前状态处于中间状态，则拒绝；如果到达终止状态，则接受。我们只需要将这个图实现就够了（下图和代码不匹配，仅供参考）。

76e2e607a9a9ea2f10b21da715ac09ea7a3c7ca6a571e75b0fab71deb204bef4-image.png

代码：
- 画出 状态转移表 ，结构为 states[n] 存储 n 个状态； - states[i] 为一个哈希表，表示从当前状态允许跳转到的下一个状态。 - 主循环中遍历字符串，通过状态转移表判断结构是否成立： - 若中途遇到无法跳转的状态，直接返回 False ； - 若成功遍历完字符串，要判断结束状态是否在允许的结束状态内，代码实现为 [2, 3, 7, 8] 。

正则匹配

Python的正则表达式

^[+-]?(\.\d+|\d+\.?\d*)([eE][+-]?\d+)?$

Python版本

  • 方法一的两种实现
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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
from typing import List

class Solution:
    def isNumber(self, s: str) -> bool:
        # 去除首尾的空字符
        s =  s.strip()
        # 检测有无除了e以外的其他字母
        ascii_a = ord('a')
        ascii_z = ord('z')
        ascii_A = ord('A')
        ascii_Z = ord('Z')
        ascii_e = ord('e')
        ascii_0 = ord('0')
        ascii_9 = ord('9')
        # 检测字母、空格、连续出现正负号
        has_number = False
        point_count = 0
        e_count = 0
        for index in range(len(s)):
            char = s[index]
            if ascii_0 <= ord(char) <= ascii_9:
                has_number = True
                continue
            if char == ' ':
                return False
            if ord(char) == ascii_e:
                e_count += 1
                if index == 0 or index == len(s)-1 or "." in s[index:]:  # e 不能在开始和结尾 也不能跟着小数
                    return False
                if index+1 == len(s)-1 and (s[index+1] == "+" or s[index+1] == "-"):
                    return False
            if ascii_a <= ord(char) <= ascii_z and ord(char) != ascii_e:
                return False
            if ascii_A <= ord(char) <= ascii_Z:
                return False
            if char == '-' or char == '+':
                if index == len(s)-1:
                    return False
                if 'e' not in s and index != 0:  # 当没有e的时候，正负号只能在第一位
                    return False
                if index+2 <= len(s) and (s[index:index+2]  == '--' or s[index:index+2]  == '++' or s[index:index+2]  == '+-' or s[index:index+2]  == '-+' or s[index:index+2]  == '-e' or s[index:index+2]  == '+e'):
                    return False
            if char == '.':
                point_count += 1
                if index+2 <= len(s) and s[index:index+2]  == '..':
                    return False
                if index+2 <= len(s) and s[index:index+2]  == '.e' and index == 0:
                    return False

        if (point_count != 0 and point_count != 1) or (e_count != 0 and e_count!= 1):
            return False

        return True if has_number else False


print("leet code accept!!!")
Input = ["459277e38+", "6ee69", "5-e95", "4e+", "46.e3", "6+1", "Re7", ".1.", ".e1", "..2", ".", "0", " 0.1 ", "abc", "1 a", "2e10", " -90e3   ", " 1e", "e3", " 6e-1", " 99e2.5 ", "53.5e93", " --6 ", "-+3", "95a54e53"]
Input1 = [2, 3]
Answer = [False, False, False, False, True, False, False, False, False, False, False, True, True, False, False, True, True, False, False, True, False, True, False, False, False]



if __name__ == "__main__":
    solution = Solution()
    for i in range(len(Input)):
        print("-"*50)
        reslut = solution.isNumber(Input[i])
        if reslut == Answer[i]:
            print(True)
        else:
            print(False)
            print(Input[i])

时间复杂度：\(O(n)\) n为输入字符串的长度
空间复杂度：\(O(1)\) 没有使用额外的空间
执行用时 :52 ms, 在所有 Python3 提交中击败了23.31%的用户
内存消耗 :13.4 MB, 在所有 Python3 提交中击败了5.56%的用户

一种更加简洁的写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def isNumber(self, s: str) -> bool:
        s = s.strip()  # 去掉两端的空白符
        if not s :
            return False
        else:
            if s[0] in ['+', '-']:
                s = s[1:]  # 去掉正负号
            if 'e' in s:
                temp_list = s.split('e')
                if len(temp_list) > 2:  # 字符串s中含有多于一个的’e‘,返回False
                    return False
                temp_list[0] = temp_list[0].replace('.', '', 1)  # 去掉e前面的字符串中的'.'
                if len(temp_list[1]) > 0 and temp_list[1][0] in ['+', '-']:  # 去掉e后面字符串中的'+'或者'-'
                    temp_list[1] = temp_list[1].replace(temp_list[1][0], '', 1)
                if temp_list[0].isnumeric() and temp_list[1].isnumeric():
                    return True
                return False
            else:  # s中不含'e'
                s = s.replace('.', '', 1)
                if s.isnumeric():
                    return True
                return False

执行用时 :40 ms, 在所有 Python3 提交中击败了61.85%的用户
内存消耗 :13.4 MB, 在所有 Python3 提交中击败了5.56%的用户

剑指offer思路的实现

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
import unittest
from typing import List



class Solution:
    def isNumber(self, s: str) -> bool:
        
        # step0：去除空格
        s = s.strip(' ')

         # step1: 拆数字 integer为整数 decimals为小数 exponent为指数
        if not s:  return False
        if s == '.':  return False
        _str = [char.lower() for char in s]  # replace E wiht e
        
        # 拆分指数部分
        if 'e' in _str:  # 有指数
            index_e = _str.index('e')
            integer = _str[:index_e]
            exponent = _str[index_e+1:]
            if '.' in exponent or 'e' in exponent or len(integer) == 0 or len(exponent) == 0:  # 有了e，exponent就不能是0了
                return False
            if len(exponent) == 1 and exponent[0] in ['+', '-']:
                return False
        else:  # 无指数
            integer = _str
            exponent = ''

        # 拆分小数部分
        if '.' in integer:  # 有小数
            index_dot = integer.index('.')
            decimals = integer[index_dot+1:]
            integer = integer[:index_dot]
            if '.' in decimals:
                return False
        else:  # 无小数
            decimals = ''


        # step3：三个部分依次检查
        is_valid = False
        if integer:
            is_valid = self.scan_digit(integer)  # 整数部分是有符号的    
        
        if decimals:
            is_valid = (is_valid or self.scan_unsgin_digit(decimals)) if len(integer) == 0 else (is_valid and self.scan_unsgin_digit(decimals))
        else:  # 如果小数部分为空，那么整数部分就不能为空了
            if len(integer) == 1 and integer[0] in ['+', '-']:
                return False

        # 检查exponent之前，必须确保integer、integer是合法的，否则就是 .e100 这种无效的情况
        if is_valid and exponent:
            is_valid = is_valid and self.scan_digit(exponent)

        return is_valid


    def scan_digit(self, number):
        if number[0] in ['+', '-']:
            number = number[1:]
        return self.scan_unsgin_digit(number)

    def scan_unsgin_digit(self, number):
        dot_count = 0
        allow_values = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']
        for i in range(len(number)):
            if number[i] not in allow_values:
                return False
            if number[i] == '.':
                dot_count += 1
            if number[i] in ['+', '-'] and i != 0:
                return False
        if dot_count > 1:
            return False
        return True



class TestSolution(unittest.TestCase):
    def setUp(self):
        self.test_class = Solution()

    def test_solution(self):
        inputs = [" -.", "+.8", "4e+", ".1", "i.1", "+-.", "6ee", ".e1", "..", "0e", "1 "]  # 特殊样例 此题的关键就在特殊测试用例
        answers = [
            False,
            True,
            False,
            True,
            False,
            False,
            False,
            False,
            False,
            False,
            True
        ]
        res = []
        for i in range(len(inputs)):
            res.append(self.test_class.isNumber(inputs[i]))
        self.assertEqual(res, answers)
 
    def tearDown(self):
        del self.test_class


if __name__ == "__main__":
    unittest.main()
  • 方法二的实现 简洁推荐该方法
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
class Solution:
    def isNumber(self, s: str) -> bool:
        # 通过有限状态机的方法 把几种字符排列情况进行了说明
        states = [
            { 'b': 0, 's': 1, 'd': 2, '.': 4 }, # 0. start  开始位置只能是 正负号('s') 数字('d') 小数点('.')
            { 'd': 2, '.': 4 } ,                # 1. 'sign' before 'e'
            { 'd': 2, '.': 3, 'e': 5, 'b': 8 }, # 2. 'digit' before 'dot'  出现数字就跳转到2 数字后面可能出现'数字'（'d': 2）、'.'（'.': 3）、'e'（'e': 5）或者直接结束（'b': 8）
            { 'd': 3, 'e': 5, 'b': 8 },         # 3. 'dot' with 'digit'
            { 'd': 3 },                         # 4. no 'digit' before 'dot'
            { 's': 6, 'd': 7 },                 # 5. 'e'  e后面可能出现的情况是正负号（'s': 6）、数字（'d': 7）
            { 'd': 7 },                         # 6. 'sign' after 'e'
            { 'd': 7, 'b': 8 },                 # 7. 'digit' after 'e'
            { 'b': 8 }                          # 8. end with
        ]
        p = 0
        for c in s:
            if '0' <= c <= '9': typ = 'd'
            elif c == ' ': typ = 'b'
            elif c == '.': typ = '.'
            elif c == 'e': typ = 'e'
            elif c in "+-": typ = 's'
            else: typ = '?'
            if typ not in states[p]: return False
            p = states[p][typ]
        return p in [2, 3, 7, 8]  # 只有以'digit' before 'dot'（以小数点之前的数字结尾）、'dot' with 'digit'（以小数点之后的数字结尾）、'digit' after 'e'（以e之后的数字结尾）、end with（正常结尾）这四种情况结束才能说明这个字符串是个正常数字

时间复杂度：\(O(n)\)
执行用时 :48 ms, 在所有 Python3 提交中击败了30.86%的用户
内存消耗 :13.4 MB, 在所有 Python3 提交中击败了5.56%的用户

  • 方法三的实现
1
2
3
4
5
import re
class Solution:
    p = re.compile(r'^[+-]?(\.\d+|\d+\.?\d*)([eE][+-]?\d+)?$')
    def isNumber(self, s: str) -> bool:
        return bool(self.p.match(s.strip()))

执行用时 :32 ms, 在所有 Python3 提交中击败了93.62%的用户
内存消耗 :13.6 MB, 在所有 Python3 提交中击败了5.56%的用户

  • 投机取巧
1
2
3
4
5
6
7
class Solution:
    def isNumber(self, s: str) -> bool:
        try:
            key=float(s)
            return True
        except:
            return False

执行用时 :36 ms, 在所有 Python3 提交中击败了82.16%的用户
内存消耗 :13.6 MB, 在所有 Python3 提交中击败了5.56%的用户

参考连接

力扣（LeetCode）jyd
力扣（LeetCode）erik_chen