0065. 有效数字
大约 4 分钟
---
0065. 有效数字
- 标签:字符串
- 难度:困难
题目链接
题目大意
描述:
一般的,一个「有效数字」可以用以下的规则之一定义:
- 一个「整数」后面跟着一个「可选指数」。
- 一个「十进制数」后面跟着一个「可选指数」。
关于「整数」、「十进制数」、「指数」、「数字」的定义:
- 一个「整数」定义为一个 「可选符号」
'-'
或'+'
后面跟着「数字」。 - 一个「十进制数」定义为一个「可选符号」
'-'
或'+'
后面跟着下述规则:- 「数字」后跟着一个 小数点
.
。 - 「数字」后跟着一个 小数点
.
再跟着「数位」。 - 一个「小数点」
.
后跟着「数位」。
- 「数字」后跟着一个 小数点
- 「指数」定义为指数符号
'e'
或'E'
,后面跟着一个 整数。 - 「数字」定义为一个或多个数位。
例如,下面的都是有效数字:
"2"
,"0089"
,"-0.1"
,"+3.14"
,"4."
,"-.9"
,"2e10"
,"-90E3"
,"3e+7"
,"+6e-1"
,"53.5e93"
,"-123.456e789"
,
下面的都不是有效数字:
"abc"
,"1a"
,"1e"
,"e3"
,"99e2.5"
,"--6"
,"-+3"
,"95a54e53"
。
给定一个字符串 。
要求:
返回 是否是一个有效数字。
说明:
- s 仅含英文字母(大写和小写),数字(0-9),加号 '+' ,减号 '-' ,或者点 '.' 。
示例:
- 示例 1:
输入:s = "0"
输出:true
- 示例 2:
输入:s = "e"
输出:false
解题思路
思路 1:有限状态自动机
核心思想:
将有效数字的识别过程建模为一个有限状态自动机(DFA),通过状态转换来判断字符串是否符合有效数字的规则。
算法步骤:
- 定义状态:定义所有可能的状态,包括开始状态、符号状态、整数部分、小数点、小数部分、指数符号、指数符号、指数整数部分等。
- 状态转换:根据当前字符类型(数字、符号、小数点、指数符号等)和当前状态,确定下一个状态。
- 接受状态:定义哪些状态是有效的结束状态。
- 遍历字符串:逐个字符处理,进行状态转换。
- 判断结果:如果最终状态是接受状态,则字符串是有效数字。
状态定义:
- :开始状态
- :符号状态(已读取
+
或-
) - :整数部分(已读取数字)
- :小数点(已读取
.
) - :小数部分(小数点后有数字)
- :指数符号(已读取
e
/E
) - :指数符号(指数部分的
+
或-
) - :指数整数部分(指数部分的数字)
状态转换规则:
- 从 :数字 → ,符号 → ,小数点 →
- 从 :数字 → ,小数点 →
- 从 :数字 → ,小数点 → ,指数符号 →
- 从 :数字 →
- 从 :数字 → ,指数符号 →
- 从 :数字 → ,符号 →
- 从 :数字 →
- 从 :数字 →
接受状态:、、(分别对应整数、小数、指数形式)
思路 1:代码
class Solution:
def isNumber(self, s: str) -> bool:
"""
使用有限状态自动机判断字符串是否为有效数字
Args:
s: 待判断的字符串
Returns:
bool: 是否为有效数字
"""
# 定义状态转换表
# 状态: 0-开始, 1-符号, 2-整数, 3-小数点, 4-小数, 5-指数符号, 6-指数符号, 7-指数整数
# 字符类型: 0-数字, 1-符号, 2-小数点, 3-指数符号, 4-其他
transitions = {
0: {0: 2, 1: 1, 2: 3, 3: -1, 4: -1}, # 开始状态
1: {0: 2, 1: -1, 2: 3, 3: -1, 4: -1}, # 符号状态
2: {0: 2, 1: -1, 2: 4, 3: 5, 4: -1}, # 整数部分
3: {0: 4, 1: -1, 2: -1, 3: -1, 4: -1}, # 小数点
4: {0: 4, 1: -1, 2: -1, 3: 5, 4: -1}, # 小数部分
5: {0: 7, 1: 6, 2: -1, 3: -1, 4: -1}, # 指数符号
6: {0: 7, 1: -1, 2: -1, 3: -1, 4: -1}, # 指数符号
7: {0: 7, 1: -1, 2: -1, 3: -1, 4: -1} # 指数整数部分
}
# 接受状态:整数、小数、指数形式
accept_states = {2, 4, 7}
# 当前状态
state = 0
# 遍历字符串
for char in s:
# 确定字符类型
if char.isdigit():
char_type = 0 # 数字
elif char in '+-':
char_type = 1 # 符号
elif char == '.':
char_type = 2 # 小数点
elif char in 'eE':
char_type = 3 # 指数符号
else:
char_type = 4 # 其他(无效字符)
# 状态转换
if state not in transitions or char_type not in transitions[state]:
return False
state = transitions[state][char_type]
# 如果转换到无效状态,直接返回 False
if state == -1:
return False
# 检查最终状态是否为接受状态
return state in accept_states
思路 1:复杂度分析
- 时间复杂度:,其中 是字符串的长度。需要遍历字符串一次,每次状态转换的时间复杂度为 。
- 空间复杂度:。状态转换表的大小是固定的,不依赖于输入字符串的长度。