signed

QiShunwang

“诚信为本、客户至上”

剑指Offer

2020/12/30 6:33:06   来源:

文章目录

  • 20. 表示数值的字符串


20. 表示数值的字符串

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

思路:构建状态机

有5种字符:

  • 空格 「 」
  • 数字「 0—9 」
  • 正负号 「 + - 」
  • 小数点 「 …」
  • 幂符号「 eE」

先写出一种包含所有情况的最全的情况:+100.3e-16,按照字符串从左到右的顺序,定义9 种状态:

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

+/-0-9.e/Eotherblank
0124-1-10
1-124-1-1-1
2-1235-18
3-13-15-18
4-13-1-1-1-1
567-1-1-1-1
6-17-1-1-1-1
7-17-1-1-18
8-1-1-1-1-18
class Solution:
    def isNumber(self, s: str) -> bool:
        if not s:return False

        transTable = [
            [1,2,4,-1,-1,0],
            [-1,2,4,-1,-1,-1],
            [-1,2,3,5,-1,8],
            [-1,3,-1,5,-1,8],
            [-1,3,-1,-1,-1,-1],
            [6,7,-1,-1,-1,-1],
            [-1,7,-1,-1,-1,-1],
            [-1,7,-1,-1,-1,8],
            [-1,-1,-1,-1,-1,8]
        ]

        cols = {
            "sign":0,
            "number":1,
            ".":2,
            "exp":3,
            "other":4,
            "blank":5  
        }

        def get_col(c):
            if c.isdigit():return 'number'
            elif c in {'+','-'}:return 'sign'
            elif c == '.':return '.'
            elif c in {'E','e'}:return 'exp'
            elif c == ' ':return 'blank'
            else:return 'other'

        legal_state = [1,2,3,4,5,8,6,7]
        # 将非法的终止状态剔除
        legal_state.remove(1)
        legal_state.remove(4)
        legal_state.remove(5)
        legal_state.remove(6)
        
        state = 0

        if len(s)==1:
            return s.isdigit()

        for c in s:
            state = transTable[state][cols[get_col(c)]]
            if state == -1:return False
        return True if state in legal_state else False

补充练习
1:LC65有效数字(与本题完全相同)
2:LC8(字符串转换整数 (atoi))
3:LC393UTF-8 编码验证