# A simple solution in Python based on DFA

• I was asked in the interview of linkedIn, writing it directly can be extremely complicated, for there are many special cases we have to deal with, and the code I wrote was messy. Then I failed to pass the interview.

Here's a clear solution. With DFA we can easily get our idea into shape and then debug, and the source code is clear and simple.

``````class Solution(object):
def isNumber(self, s):
"""
:type s: str
:rtype: bool
"""
#define a DFA
state = [{},
{'blank': 1, 'sign': 2, 'digit':3, '.':4},
{'digit':3, '.':4},
{'digit':3, '.':5, 'e':6, 'blank':9},
{'digit':5},
{'digit':5, 'e':6, 'blank':9},
{'sign':7, 'digit':8},
{'digit':8},
{'digit':8, 'blank':9},
{'blank':9}]
currentState = 1
for c in s:
if c >= '0' and c <= '9':
c = 'digit'
if c == ' ':
c = 'blank'
if c in ['+', '-']:
c = 'sign'
if c not in state[currentState].keys():
return False
currentState = state[currentState][c]
if currentState not in [3,5,8,9]:
return False
return True
``````

• So many cases...
How about doing something really magic with python?

``````    try:
float(s)
return True
except:
return False``````

• in the interview, this is not what they want.

• Why not start from state 0? Seems waste one state.

• Very cool solution. I picked it apart and made it (overly) explicit:

``````class Solution(object):
def isNumber(self, s):
"""
:type s: str
:rtype: bool
"""
#define DFA state transition tables
states = [{},
# State (1) - initial state (scan ahead thru blanks)
{'blank': 1, 'sign': 2, 'digit':3, '.':4},
# State (2) - found sign (expect digit/dot)
{'digit':3, '.':4},
# State (3) - digit consumer (loop until non-digit)
{'digit':3, '.':5, 'e':6, 'blank':9},
# State (4) - found dot (only a digit is valid)
{'digit':5},
# State (5) - after dot (expect digits, e, or end of valid input)
{'digit':5, 'e':6, 'blank':9},
# State (6) - found 'e' (only a sign or digit valid)
{'sign':7, 'digit':8},
# State (7) - sign after 'e' (only digit)
{'digit':8},
# State (8) - digit after 'e' (expect digits or end of valid input)
{'digit':8, 'blank':9},
# State (9) - Terminal state (fail if non-blank found)
{'blank':9}]
currentState = 1
for c in s:
# If char c is of a known class set it to the class name
if c in '0123456789':
c = 'digit'
elif c in ' \t\n':
c = 'blank'
elif c in '+-':
c = 'sign'
# If char/class is not in our state transition table it is invalid input
if c not in states[currentState]:
return False
# State transition
currentState = states[currentState][c]
# The only valid terminal states are end on digit, after dot, digit after e, or white space after valid input
if currentState not in [3,5,8,9]:
return False
return True
``````

• you are very funny, and python is very powerful! so python get 100 scores, and u get 0! lol

• OMG, Just Brilliant!

• So brilliant... Reading this post make me feel that I've forgot everything learnt from my digital circus course... especially the merging states part. I ended up with a long long code of over 10 states for this problem lol.

• @shenggu is your Last Name Lu?

• @heqingy wo qu dou mei you kan dao ID...

• Cool. This picture is something like FSA.

• something wrong. this dfa return wrong result when input is "0123"

• @yearss For me, it returns True, which is correct for this problem.

If you doubt whether "0123" is a valid number, check the definition of "number" in language such as C/C++, python

• Great idea, here is my implementation.

``````class Solution(object):
def isNumber(self, s):
"""
:type s: str
:rtype: bool
"""
states = [
{' ': 0, 'sign': 1, 'digit': 2, '.': 3},
{'digit': 2, '.': 3},
{'digit': 2, '.': 4, 'e': 5, ' ': 8},
{'digit': 4},
{'digit': 4, 'e': 5, ' ': 8},
{'sign': 6, 'digit': 7},
{'digit': 7},
{'digit': 7, ' ': 8},
{' ': 8}
]
cur = 0
for c in s:
if c == '+' or c == '-':
c = 'sign'
elif '0' <= c <= '9':
c = 'digit'
if c not in states[cur].keys():
return False
cur = states[cur][c]
return cur in [2, 4, 7, 8]
``````

• Is that possible that the string starts with "e"(eg, e-10)?

• In terms of q3-->q5 and q4-->5, I am confused that why q3 and q4 could point to same q5?

• @Henry456 It depends on the definition of "valid number". At least, in most popular languages, I don't see any valid number starting with 'e'

• @Henry456 why not? it's just a state transition graph.

• @aynamron can you make up a number consistent with both q3-->q5 and q4-->q5? I still cannot get it! Thanks!

• @Henry456 you'd better review how DFA works and what this graph means. There's no such a number that matches both parallel paths.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.