LeetCode 65：有效数字
问题本质与挑战
需判断字符串是否为有效数字，规则涉及整数、小数、指数（e/E）的复杂组合，如：
- 整数：
+123、-45、678 - 小数：
1.2、.3、4.、5.6 - 指数：
1e10、2E-3、3.e4
核心难点：规则分支多（符号、小数点、指数的组合），需用状态机清晰建模所有合法转移。
核心思路：状态机（DFA）
将判断过程拆解为状态转移：
- 状态定义：每个状态代表当前解析的“阶段”（如“初始状态”“整数部分”“小数部分”等）。
- 输入类型：将字符分为 6 类（空格、符号、数字、小数点、指数
e/E、非法字符）。 - 转移规则：定义从一个状态到另一个状态的合法转移（如“初始状态”遇到符号→“符号后状态”）。
- 终止状态：遍历完字符串后，若处于合法终止状态（如“整数结束”“小数结束”“指数整数结束”），则为有效数字。
状态机设计（详细状态与转移）
1. 状态枚举（10 个核心状态）
enum State {// 初始状态（可空格、符号、数字、小数点）START,// 符号后（需接数字或小数点）SIGN,// 整数部分（可接数字、小数点、指数、空格）INTEGER,// 小数点前无数字（如 .123，需接数字）DOT_WITHOUT_INT,// 小数点后（如 123.，需接数字；或 123.456，可接数字、指数、空格）DOT_WITH_INT,// 指数符号后（需接符号或数字）EXP,// 指数符号后的符号（需接数字）EXP_SIGN,// 指数的整数部分（需接数字、空格）EXP_INT,// 末尾空格（需结束）END_SPACE,// 非法状态（遇到非法字符，直接终止）INVALID
}
2. 输入类型分类（6 类）
private InputType getInputType(char c) {if (c == ' ') return InputType.SPACE;if (c == '+' || c == '-') return InputType.SIGN;if (Character.isDigit(c)) return InputType.DIGIT;if (c == '.') return InputType.DOT;if (c == 'e' || c == 'E') return InputType.EXP;return InputType.INVALID; // 非法字符（如字母、特殊符号）
}
3. 状态转移表（核心逻辑）
用二维数组 trans 定义状态转移规则：trans[当前状态][输入类型] = 下一状态。
示例转移（部分关键规则）：
START状态遇到SPACE→ 保持START（前导空格）。START状态遇到SIGN→ 转移到SIGN（符号后需接数字或小数点）。INTEGER状态遇到DOT→ 转移到DOT_WITH_INT（整数后接小数点，如123.）。EXP状态遇到SIGN→ 转移到EXP_SIGN（指数符号后接符号，如e-）。
算法步骤详解
步骤 1：初始化状态机
State currentState = State.START; // 初始状态
步骤 2：遍历字符串，逐字符转移状态
for (char c : s.toCharArray()) {InputType type = getInputType(c);currentState = trans[currentState.ordinal()][type.ordinal()]; // 状态转移if (currentState == State.INVALID) break; // 非法状态，提前终止
}
步骤 3：检查终止状态
合法终止状态需满足：
INTEGER（纯整数，如123）DOT_WITH_INT（小数，如123.、123.456）EXP_INT（指数整数，如1e10）END_SPACE（末尾空格，如123）
return currentState == State.INTEGER || currentState == State.DOT_WITH_INT || currentState == State.EXP_INT || currentState == State.END_SPACE;
完整代码（Java）
class Solution {// 输入类型枚举（空格、符号、数字、小数点、指数、非法）enum InputType { SPACE, SIGN, DIGIT, DOT, EXP, INVALID }// 状态枚举（详细见思路）enum State {START, SIGN, INTEGER, DOT_WITHOUT_INT, DOT_WITH_INT,EXP, EXP_SIGN, EXP_INT, END_SPACE, INVALID}// 状态转移表：[当前状态][输入类型] → 下一状态private final State[][] trans = {// 输入类型顺序：SPACE, SIGN, DIGIT, DOT, EXP, INVALID{State.START, State.SIGN, State.INTEGER, State.DOT_WITHOUT_INT, State.INVALID, State.INVALID}, // START{State.INVALID, State.INVALID, State.INTEGER, State.DOT_WITHOUT_INT, State.INVALID, State.INVALID}, // SIGN{State.END_SPACE, State.INVALID, State.INTEGER, State.DOT_WITH_INT, State.EXP, State.INVALID}, // INTEGER{State.INVALID, State.INVALID, State.DOT_WITH_INT, State.INVALID, State.INVALID, State.INVALID}, // DOT_WITHOUT_INT{State.END_SPACE, State.INVALID, State.DOT_WITH_INT, State.INVALID, State.EXP, State.INVALID}, // DOT_WITH_INT{State.INVALID, State.EXP_SIGN, State.EXP_INT, State.INVALID, State.INVALID, State.INVALID}, // EXP{State.INVALID, State.INVALID, State.EXP_INT, State.INVALID, State.INVALID, State.INVALID}, // EXP_SIGN{State.END_SPACE, State.INVALID, State.EXP_INT, State.INVALID, State.INVALID, State.INVALID}, // EXP_INT{State.END_SPACE, State.INVALID, State.INVALID, State.INVALID, State.INVALID, State.INVALID}, // END_SPACE{State.INVALID, State.INVALID, State.INVALID, State.INVALID, State.INVALID, State.INVALID} // INVALID};public boolean isNumber(String s) {State currentState = State.START;for (char c : s.toCharArray()) {InputType type = getInputType(c);currentState = trans[currentState.ordinal()][type.ordinal()];if (currentState == State.INVALID) break; // 非法状态提前终止}// 合法终止状态：整数、小数、指数整数、末尾空格return currentState == State.INTEGER || currentState == State.DOT_WITH_INT || currentState == State.EXP_INT || currentState == State.END_SPACE;}// 将字符分类为输入类型private InputType getInputType(char c) {if (c == ' ') return InputType.SPACE;if (c == '+' || c == '-') return InputType.SIGN;if (Character.isDigit(c)) return InputType.DIGIT;if (c == '.') return InputType.DOT;if (c == 'e' || c == 'E') return InputType.EXP;return InputType.INVALID;}
}
关键代码解释
1. 枚举定义
InputType：将字符分类，简化状态转移的条件判断。State：定义解析过程的所有阶段，覆盖合法/非法转移的所有情况。
2. 状态转移表 trans
二维数组存储状态转移规则，trans[当前状态][输入类型] 直接返回下一状态，避免大量 if-else 判断。
3. 主逻辑 isNumber
- 初始化状态为
START，逐字符处理：- 用
getInputType分类字符，查转移表更新状态。 - 若遇到非法状态，直接终止遍历。
- 用
- 最后检查是否处于合法终止状态（覆盖所有有效数字的结束情况）。
状态转移示例（以 s = " 123.45e-6 " 为例）
| 字符 | 输入类型 | 当前状态 → 下一状态 | 解释 |
|---|---|---|---|
| SPACE | START → START | 前导空格，保持初始状态 |
1 | DIGIT | START → INTEGER | 初始状态遇数字，进入整数 |
2 | DIGIT | INTEGER → INTEGER | 整数部分延续 |
3 | DIGIT | INTEGER → INTEGER | 整数部分延续 |
. | DOT | INTEGER → DOT_WITH_INT | 整数后接小数点 |
4 | DIGIT | DOT_WITH_INT → DOT_WITH_INT | 小数部分延续 |
5 | DIGIT | DOT_WITH_INT → DOT_WITH_INT | 小数部分延续 |
e | EXP | DOT_WITH_INT → EXP | 小数后接指数符号 |
- | SIGN | EXP → EXP_SIGN | 指数符号后接负号 |
6 | DIGIT | EXP_SIGN → EXP_INT | 负号后接数字，进入指数整数 |
| SPACE | EXP_INT → END_SPACE | 指数整数后接空格 |
遍历结束后，状态为 END_SPACE，属于合法终止状态 → 有效数字。
复杂度分析
- 时间复杂度：
O(n)（遍历字符串一次，状态转移O(1)）。 - 空间复杂度：
O(1)（状态和转移表为固定大小）。
总结
状态机是处理复杂规则匹配的“万能钥匙”，通过清晰的状态定义和转移规则，将有效数字的判断转化为状态转移路径的合法性检查。该方法不仅解决问题，还能通过状态枚举覆盖所有边界情况（如 .1、1.、1e10 等），是字符串解析类问题的经典解决方案。
