Comment on page
0065. 有效数字
https://leetcode-cn.com/problems/valid-number/
有效数字（按顺序）可以分成以下几个部分：
一个 小数 或者 整数
（可选）一个 '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 ，如果 s 是一个 有效数字 ，请返回 true 。
示例 1：
输入：s = "0"
输出：true
示例 2：
输入：s = "e"
输出：false
示例 3：
输入：s = "."
输出：false
示例 4：
输入：s = ".1"
输出：true
提示：
1 <= s.length <= 20
s 仅含英文字母（大写和小写），数字（0-9），加号 '+' ，减号 '-' ，或者点 '.' 。
- 暂无
- 暂无
我们可以直接进行一次遍历，边遍历边判断是否合法。
如果要边遍历边判断是否合法则需要记录一些关键信息。比如，当我遍历途中遇到了 .，那么我实际上需要知道一些信息，比如前面是否已经出现过 . 了。如果已经出现过了，那么就可以得出结论，该数字非法。
除了前面是否出现 . 这样的信息，我们还需要关注其他信息。具体地，我们需要关注：
- .
- e/E
- 前面是否有数字
以上三个信息。 我们可以用三个变量，分别表示上一次遇到其的位置（索引），用 -1 表示还没有遇到。
实际上，这道题的关键点就是分析出哪些是非法，这样不是非法的，那么就是合法的。 之所以如此是因为合法的实在是太多了，我们没有办法一一判断，而只能从非法的角度入手。而非法的情况比较多，如何分类是个问题，这也是本题是困难难度的原因。
让我们来分析一下非法的情景。
- 点前面有 e 或者 点，比如 1.1.1 或者 3e5.2
- e 前面有 e ，比如 e12e。或者 e 前面没有数字，比如 e123
+ -前面要么是 e，要么其位于第一位- 出现了非法字符。也就是出现了除了 +-eE 数字. 之外的字符
代码上，我们可以使用三个变量：
- 1.last_dot 上一次遇到的 . 的位置
- 2.last_e 上一次遇到的 e/E 的位置
- 3.last_d 上一次遇到的数字的位置
接下来我们需要遍历字符串 s，遍历的同时记得更新三个变量。
- 如果我们遇到了字符 "."，那么需要前面没有 "."，也不能有 e/E，否则就不合法。
- 如果遇到了 e/E，那么前面不能有 e/E。除此之前前面还有有数字才行。
- 如果遇到了 +-，要么它是第一个字符，要么它前面是 e/E，否则不能合法
- 其他非数字字符均为不合法
- 分析非法的情况，用三个变量记录上一次出现的点，指数，数字的位置来复制判断
class Solution:
def isNumber(self, s: str) -> bool:
last_dot = last_e = last_d = -1
for i, c in enumerate(s):
if c.isdigit():
last_d = i
elif c == '.':
if last_dot != -1 or last_e != -1: return False
last_dot = i
elif c.lower() == 'e':
if last_d == -1 or last_e != -1: return False
last_e = i
elif c == '+' or c == '-':
if i == 0 or s[i-1].lower() == 'e':
continue
else:
return False
else:
return False
return s[-1].isdigit() or (s[-1] == '.' and last_d != -1)
复杂度分析
令 n 为数组长度。
- 时间复杂度：$O(n)$
- 空间复杂度：$O(1)$
对于状态机，我们需要解决的就是：
- 1.状态有哪些
- 2.选择有哪些
和动态规划是类似的
对于这道题来说，打底的状态就是各种字符的类型。即：
- 数字
- .
- eE
- +-
打底就是这四种。
我们没有必要将 eE 或者 +- 进行区分，这是因为在这里二者的逻辑不会有差别。
那么这四种就够了。这是不够的。这是因为题目描述决定的。比如题目说了 e 后面不能是小数。 那么对于 . 来说，
- 我们就需要分裂 为两种状态： e 前面的 . 和 e 后面的 .。
- 类似地，+- 号，我们需要区分是第一位还是 e 后面的（紧邻），这是因为第一位后面可以跟 . ，而 e 后面紧邻的不可以。
- 数字也是一样。 由于 e 后面不能有点，也需要进行类似的分裂
最后一个比较容易漏掉，我们需要一种数字状态，这个数字状态后面只能跟数字，不能跟其他。比如 +2e+3 ，这个时候的 3 后面就只能是数字了，其他都是非法的。
对于这道题来说：
- 图中黄色的四个部分就是选择。由于 +-，以及 [1-9] 对我们的算法没有影响，因此没有单独抽离出来，而是将其归为一类。
- 图中虚线部分就是状态。
不难看出，"." 前后的状态选择是不同的。因此除了："+-", "[1-9]", "e/E", "." 这几种基本状态，还要分别对 [1-9], e/E 进行区分是 “.”前还是后。从左到右我将其进行编号，靠左的是 1，靠右的是 2, 因此就有了 sign1,digit1, exp, D digit2 exp sign2 D 的状态命名。
注意这里是 D，不是 digit2。因为 digit2 可以接 E/e，因此需要单独定义一种状态
另外由于：dot 前面和后面必须有至少一个数字，并且有没有数字对选择也有影响，因此我们也需要对此区分。我这里用 dot1 表示前面有数字的 dot，dot2 表示前面没有数字的 dot
关于如何转化，我就不一一分析了，大家直接看代码吧。虽然思路不难理解，但是细节还是蛮多的，大家自己写写就知道了。
- 建立状态机模型
- 如果知道一共有多少状态
代码上，我们 xxx1 表示前面的 xxx，xxx2 表示后面的 xxx。D 表示只能跟数字
- 语言支持：Python3
Python3 Code:
class Solution:
def isNumber(self, s: str) -> bool:
# 任何状态机的核心都是建立如下的状态机模型
states = {
"start": {"SIGN":"sign1", "DIGIT":"digit1", "DOT":"dot1"},
"sign1": {"DIGIT":"digit1", "DOT":"dot1"},
"sign2": {"DIGIT":"D"},
"digit1": {"DIGIT":"digit1", "DOT":"dot2", "EXP":"exp", "END": True},
"digit2": {"DIGIT":"digit2", "EXP":"exp", "END": True},
"dot1": {"DIGIT":"digit2"}, # 前面没数字
"dot2": {"DIGIT":"digit2", "EXP":"exp", "END": True}, # 前面有数字
"exp": {"SIGN":"sign2", "DIGIT":"D"},
"D": {"DIGIT":"D", "END": True}
}
def get(ch):
if ch == ".": return "DOT"
elif ch in "+-": return "SIGN"
elif ch in "Ee": return "EXP"
elif ch.isdigit(): return "DIGIT"
state = "start"
for c in s:
state = states[state].get(get(c))
if not state: return False
return "END" in states[state]
复杂度分析
令 n 为数组长度。
- 时间复杂度：$O(n)$
- 空间复杂度：虽然使用了 states 存放状态，但是其不会随着 数字增大而变大，而是一个定值，因此空间复杂度为 $O(1)$
以上就是本文的全部内容了。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
最近更新 10mo ago