65. 有效数字
验证给定的字符串是否可以解释为十进制数字。
例如:
"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
说明: 我们有意将问题陈述地比较模糊。在实现代码之前,你应当事先思考所有可能的情况。这里给出一份可能存在于有效十进制数字中的字符列表:
数字 0-9
指数 - "e"
正/负号 - "+"/"-"
小数点 - "."
当然,在输入中,这些字符的上下文也很重要。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/valid-number/
Link:https://leetcode.com/problems/valid-number/
依次判断
O(N)
class Solution:
def isNumber(self, s: str) -> bool:
s = s.strip()
i = 0
# 符号位
if i < len(s) and (s[i] == '+' or s[i] == '-'):
i += 1
# 数字
point_count = 0
digit_count = 0
while i < len(s) and ('0' <= s[i] <= '9' or s[i] == '.'):
if s[i] == '.':
point_count += 1
else:
digit_count += 1
i += 1
if point_count > 1 or digit_count < 1:
return False
# 指数位
if i < len(s) and s[i] == 'e':
i += 1
if i < len(s) and (s[i] == '+' or s[i] == '-'):
i += 1
digit_count = 0
while i < len(s) and '0' <= s[i] <= '9':
digit_count += 1
i += 1
if digit_count < 1:
return False
return i == len(s)
正则表达式
参考:https://leetcode.com/problems/valid-number/discuss/23728/A-simple-solution-in-Python-based-on-DFA
import re
class Solution:
def isNumber(self, s: str) -> bool:
return re.search(r'^\s*[+-]?(\d+(\.\d*)?|\.\d+)(e[+-]?\d+)?\s*$', s)
有限自动机
blank +/- digit . digit e +/- digit blank
1 2 3 4 5 6 7 8 9
状态转换
1 -> blank=1, sign=2, digit=3, dot=4
2 -> digit=3, dot=4
3 -> digit=3, dot=4, e=6, blank=9 # ⚠️这里dot的转移状态和社区大神的不一致, 但个人觉得更好理解
4 -> digit=5
5 -> digit=5, e=6, blank=9
6 -> sign=7, digit=8
7 -> digit=8
8 -> digit=8, blank=9
9 -> blank=9
结束状态
3, 5, 8, 9 4 比较特殊, 如果遇到过数字,就是有效结束状态
class Solution:
def isNumber(self, s: str) -> bool:
table = [{},
{'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}]
state = 1
digit_seen = False
for c in s:
if '0' <= c <= '9':
c = 'digit'
digit_seen = True
if c == ' ':
c = 'blank'
if c in ['+', '-']:
c = 'sign'
if c not in table[state].keys():
return False
state = table[state][c]
return state in [3, 5, 8, 9] or (state == 4 and digit_seen)
–End–