forked from shijbian/LeetCode
-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy pathvalid-number.py
More file actions
119 lines (105 loc) · 3.76 KB
/
valid-number.py
File metadata and controls
119 lines (105 loc) · 3.76 KB
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
# Time: O(n)
# Space: O(1)
#
# 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.
#
class InputType:
INVALID = 0
SPACE = 1
SIGN = 2
DIGIT = 3
DOT = 4
EXPONENT = 5
# regular expression: "^\s*[\+-]?((\d+(\.\d*)?)|\.\d+)([eE][\+-]?\d+)?\s*$"
# automata: http://images.cnitblog.com/i/627993/201405/012016243309923.png
class Solution(object):
def isNumber(self, s):
"""
:type s: str
:rtype: bool
"""
transition_table = [[-1, 0, 3, 1, 2, -1], # next states for state 0
[-1, 8, -1, 1, 4, 5], # next states for state 1
[-1, -1, -1, 4, -1, -1], # next states for state 2
[-1, -1, -1, 1, 2, -1], # next states for state 3
[-1, 8, -1, 4, -1, 5], # next states for state 4
[-1, -1, 6, 7, -1, -1], # next states for state 5
[-1, -1, -1, 7, -1, -1], # next states for state 6
[-1, 8, -1, 7, -1, -1], # next states for state 7
[-1, 8, -1, -1, -1, -1]] # next states for state 8
state = 0
for char in s:
inputType = InputType.INVALID
if char.isspace():
inputType = InputType.SPACE;
elif char == '+' or char == '-':
inputType = InputType.SIGN
elif char.isdigit():
inputType = InputType.DIGIT
elif char == '.':
inputType = InputType.DOT
elif char == 'e' or char == 'E':
inputType = InputType.EXPONENT;
state = transition_table[state][inputType];
if state == -1:
return False;
return state == 1 or state == 4 or state == 7 or state == 8
class Solution2(object):
def isNumber(self, s):
"""
:type s: str
:rtype: bool
"""
import re
return bool(re.match("^\s*[\+-]?((\d+(\.\d*)?)|\.\d+)([eE][\+-]?\d+)?\s*$", s))
if __name__ == "__main__":
print Solution().isNumber(" 0.1 ")
print Solution().isNumber("abc")
print Solution().isNumber("1 a")
print Solution().isNumber("2e10")
# public class Solution {
# public boolean isNumber(String s) {
# int len = s.length();
# int i = 0, e = len - 1;
# while (i <= e && Character.isWhitespace(s.charAt(i))) i++;
# if (i > len - 1) return false;
# while (e >= i && Character.isWhitespace(s.charAt(e))) e--;
# // skip leading +/-
# if (s.charAt(i) == '+' || s.charAt(i) == '-') i++;
# boolean num = false; // is a digit
# boolean dot = false; // is a '.'
# boolean exp = false; // is a 'e'
# while (i <= e) {
# char c = s.charAt(i);
# if (Character.isDigit(c)) {
# num = true;
# }
# else if (c == '.') {
# if(exp || dot) return false;
# dot = true;
# }
# else if (c == 'e') {
# if(exp || num == false) return false;
# exp = true;
# num = false;
# }
# else if (c == '+' || c == '-') {
# if (s.charAt(i - 1) != 'e') return false;
# }
# else {
# return false;
# }
# i++;
# }
# return num;
# }
# }