leetcode65-valid-number

Posted on | In

Description

Validate if a given string is numeric.

Some examples:
“0” => true
“ 0.1 “ => true
“abc” => false
“1 a” => false
“2e10” => true

Note: It is intended for the problem statement to be ambiguous. You should gather all requirements up front before implementing one.

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.

Idea

Deterministic finite automaton (DFA) — natural language processing

Code

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
class Solution(object):
    def __init__(self):
        self.states = [{}, 
                  {'blank':1, 'digit':3, 'sign':2, 'dot':4}, 
                  {'digit':3, 'dot':4},
                  {'digit':3, 'blank':9, 'e':6, 'dot':5},
                  {'digit':5},
                  {'digit':5, 'e':6, 'blank':9},
                  {'sign':7, 'digit':8},
                  {'digit':8}, 
                  {'digit':8, 'blank':9},
                  {'blank':9}]
        
    def isNumber(self, s):
        """
        :type s: str
        :rtype: bool
        """
        cur_q = 1
        for c in s:
            if c in '0123456789':
                state = 'digit'
            elif c in '-+':
                state = 'sign'
            elif c == '.':
                state = 'dot'
            elif c == ' ':
                state = 'blank'
            elif c == 'e':
                state = 'e'
            else:
                return False
            if not (state in self.states[cur_q]):
                return False
            cur_q = self.states[cur_q][state]
        if not (cur_q in [3, 5, 8, 9]):
            return False
        return True