DFA - Easy¶
Github | https://github.com/newsteinking/leetcode
65. Valid Number¶
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.
=================================================================
class States(object):
def __init__(self):
self.init = 0
self.decimal = 1
self.decpoint = 2
self.afterdp = 3
self.e = 4
self.aftere = 5
self.sign = 6
self.nullpoint = 7
self.esign = 8
self.afteresign = 9
class Solution(object):
def isNumber(self, s):
"""
:type s: str
:rtype: bool
"""
s = s.strip()
states = States()
state = states.init
decimals = "01234567890"
for c in s:
if state == states.init:
if c == ".":
state = states.nullpoint
elif c in decimals:
state = states.decimal
elif c in ["+", "-"]:
state = states.sign
else:
return False
elif state == states.sign:
if c in decimals:
state = states.decimal
elif c == ".":
state = states.nullpoint
else:
return False
elif state == states.esign:
if c not in decimals:
return False
state = states.afteresign
elif state == states.afteresign:
if c not in decimals:
return False
elif state == states.nullpoint:
if c not in decimals:
return False
state = states.decpoint
elif state == states.decimal:
if c in decimals:
continue
elif c == "e":
state = states.e
elif c == ".":
state = states.decpoint
else:
return False
elif state == states.decpoint:
if c in decimals:
state = states.afterdp
elif c == "e":
state = states.e
else:
return False
elif state == states.afterdp:
if c in decimals:
continue
elif c == "e":
state = states.e
else:
return False
elif state == states.e:
if c in decimals:
state = states.aftere
elif c in ["+", "-"]:
state = states.esign
else:
return False
elif state == states.aftere:
if c not in decimals:
return False
else:
return False
return state not in [states.init, states.e, states.nullpoint, states.sign, states.esign]
=================================================================
class Solution(object):
def isNumber(self, s):
"""DFA
Details can be found here:
https://github.com/xuelangZF/LeetCode/blob/master/Images/65_ValidNumber.png
https://github.com/xuelangZF/LeetCode/blob/master/Images/65_StateConvert.png
"""
s = s.strip()
if not s:
return False
# DFA states change table
DFA_states_change = {
0: {1: 2, 2: 1, 3: 8, 4: -1},
1: {1: 2, 2: -1, 3: 8, 4: -1},
2: {1: 2, 2: -1, 3: 3, 4: 5},
3: {1: 4, 2: -1, 3: -1, 4: 5},
4: {1: 4, 2: -1, 3: -1, 4: 5},
5: {1: 7, 2: 6, 3: -1, 4: -1},
6: {1: 7, 2: -1, 3: -1, 4: -1},
7: {1: 7, 2: -1, 3: -1, 4: -1},
8: {1: 4, 2: -1, 3: -1, 4: -1}
}
current_state = 0
for char in s:
input_num = self.input_num(char)
if not input_num:
return False
next_state = DFA_states_change[current_state][input_num]
if next_state == -1:
return False
current_state = next_state
if (current_state == 2 or current_state == 3 or
current_state == 4 or current_state == 7):
return True
else:
return False
def input_num(self, char):
if char in "0123456789":
return 1
elif char in "+-":
return 2
elif char == ".":
return 3
elif char == "e":
return 4
else:
return 0
# True
"""
" .1"
"012"
"+12"
"-12"
"12e1"
"12e-1"
"12e+1"
"12e0"
"0e1"
"-1e1"
"1.2"
".2"
".1e1"
"+.2"
"1."
" .1 "
"46.e3"
"""