LeetCode 65：有效数字

LeetCode 65：有效数字

问题本质与挑战

需判断字符串是否为有效数字，规则涉及整数、小数、指数（e/E）的复杂组合，如：

• 整数：+123、-45、678
• 小数：1.2、.3、4.、5.6
• 指数：1e10、2E-3、3.e4

核心难点：规则分支多（符号、小数点、指数的组合），需用状态机清晰建模所有合法转移。

核心思路：状态机（DFA）

将判断过程拆解为状态转移：

1. 状态定义：每个状态代表当前解析的“阶段”（如“初始状态”“整数部分”“小数部分”等）。
2. 输入类型：将字符分为 6 类（空格、符号、数字、小数点、指数 e/E、非法字符）。
3. 转移规则：定义从一个状态到另一个状态的合法转移（如“初始状态”遇到符号→“符号后状态”）。
4. 终止状态：遍历完字符串后，若处于合法终止状态（如“整数结束”“小数结束”“指数整数结束”），则为有效数字。

状态机设计（详细状态与转移）

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 等），是字符串解析类问题的经典解决方案。