算法题--验证数字的合法性

image.png

0. 链接

题目链接

1. 题目

Validate if a given string can be interpreted as a decimal number.

Some examples:

"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

Note: It is intended for the problem statement to be ambiguous. You should gather all requirements up front before implementing one. However, here is a list of characters that can be in a valid decimal number:

Numbers 0-9
Exponent - "e"
Positive/negative sign - "+"/"-"
Decimal point - "."
Of course, the context of these characters also matters in the input.

Update (2015-02-10):
The signature of the C++ function had been updated. If you still see your function signature accepts a const char * argument, please click the reload button to reset your code definition.

2. 思路1：状态机

按照开头是否是., 是否包含e, 是否包含-/+, 尾部是否为空格等条件，细分为10个状态

3. 代码

# coding:utf8

class Solution:
    def isNumber(self, s: str) -> bool:
        # -/+ | 空格 | . | e | 0-9
        ch_col_dict = {
            '-': 0,
            '+': 0,
            ' ': 1,
            '.': 2,
            'e': 3
        }
        for i in range(10):
            ch_col_dict[str(i)] = 4

        nfa = [
            [0, 0, 0, 0, 0],        # 0. 空白状态
            [2, 1, 3, 0, 6],        # 1. 初始状态, 尚未遇到非空格合法字符
            [0, 0, 3, 0, 6],        # 2. 前面只有一个-/+
            [0, 0, 0, 0, 8],        # 3. 前面只有一个.
            [5, 0, 0, 0, 7],        # 4. 前面是一个合法数字(开头可能包含-/+)再跟着一个e
            [0, 0, 0, 0, 7],        # 5. 前面是一个合法数字(开头可能包含-/+), 再跟着一个e-/+
            [0, 9, 8, 4, 6],        # 6. 前面是一个合法数字, 不包含e
            [0, 9, 0, 0, 7],        # 7. 前面是一个合法数字, 包含了e
            [0, 9, 0, 4, 8],        # 8. 前面是一个合法数字, 构成是一个.跟着若干个数字
            [0, 9, 0, 0, 0]         # 9. 前面是一个合法数字, 且尾部已经是空格, 数字的值已经确定下来
        ]
        state = 1
        for i in range(len(s)):
            ch = s[i]
            j = 0
            if ch in ch_col_dict:
                j = ch_col_dict[ch]
            else:
                return False
            state = nfa[state][j]
            if state == 0:
                return False

        return state >= 6


test_cases = ['0 ',
                ' 0.1  ',
                'abc ',
                '1 a ',
                '2e10 ',
                ' -90e3    ',
                ' 1e ',
                'e3 ',
                ' 6e-1 ',
                ' 99e2.5  ',
                '53.5e93 ',
                ' --6  ',
                '-+3 ',
                '95a54e53 ',
                ' ',
                '.1',
                '1.',
                '46.e3',
                ' -.7e+0435'
              ]


solution = Solution()
for s in test_cases:
    print('"{}" => {}'.format(s, solution.isNumber(s)))

输出结果

"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
" " => False
".1" => True
"1." => True
"46.e3" => True
" -.7e+0435" => True

4. 结果

image.png