# 0065. 有效数字

### 题目地址(65. 有效数字)

<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，否则不能合法
* 其他非数字字符均为不合法

#### 关键点

* 分析非法的情况，用三个变量记录上一次出现的点，指数，数字的位置来复制判断

#### 代码

```py
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)$

### 状态机

#### 思路

![](https://p.ipic.vip/tzx4ia.jpg)

对于状态机，我们需要解决的就是：

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:

```python

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)$

> 此题解由 [力扣刷题插件](https://leetcode-pp.github.io/leetcode-cheat/?tab=solution-template) 自动生成。

力扣的小伙伴可以[关注我](https://leetcode-cn.com/u/fe-lucifer/)，这样就会第一时间收到我的动态啦\~

以上就是本文的全部内容了。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：<https://github.com/azl397985856/leetcode> 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。

关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。

![](https://p.ipic.vip/57bg3l.jpg)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/hard/65.valid-number.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.