#include <string>
#include <vector>
#include <unordered_map>
using namespace std;class Solution {
public:bool isNumber(string s) {// 定义状态转移表vector<unordered_map<char, int>> states = {{{' ', 0}, {'s', 1}, {'d', 2}, {'.', 4}}, // 状态0:初始状态{{'d', 2}, {'.', 4}}, // 状态1:符号位{{'d', 2}, {'.', 3}, {'e', 5}, {' ', 8}}, // 状态2:整数部分{{'d', 3}, {'e', 5}, {' ', 8}}, // 状态3:小数部分(有整数部分){{'d', 3}}, // 状态4:小数部分(无整数部分){{'s', 6}, {'d', 7}}, // 状态5:指数符号{{'d', 7}}, // 状态6:指数符号后的符号位{{'d', 7}, {' ', 8}}, // 状态7:指数部分{{' ', 8}} // 状态8:结尾空格};int currentState = 0;for (char c : s) {char type;if (isdigit(c)) type = 'd';else if (c == '+' || c == '-') type = 's';else if (c == 'e' || c == 'E') type = 'e';else if (c == '.') type = '.';else if (c == ' ') type = ' ';else return false; // 非法字符if (states[currentState].find(type) == states[currentState].end()) {return false; // 无法转移到下一个状态}currentState = states[currentState][type];}// 最终有效状态:2(整数)、3(小数)、7(指数)、8(结尾空格)return currentState == 2 || currentState == 3 || currentState == 7 || currentState == 8;}
};
代码解析:使用确定有限状态自动机验证有效数字
这段代码通过**确定有限状态自动机(DFA)**来验证一个字符串是否表示有效数字。下面我将从状态定义、转移规则到完整逻辑逐步解析:
一、整体思路
DFA 是一种计算模型,它包含:
- 状态集合:不同处理阶段(如初始状态、符号位、整数部分等)
- 转移规则:基于当前状态和输入字符决定下一个状态
- 初始状态:验证开始的状态
- 接受状态:验证成功的最终状态
这个解法将字符串处理过程划分为9个状态,通过转移表定义状态间的转换规则,最终根据结束状态判断是否有效。
二、状态定义与转移表
1. 状态定义
状态用整数表示(0-8),每个状态对应数字字符串的一个解析阶段:
- 0:初始状态(可接受空格、符号、数字、小数点)
- 1:符号位(+/-)
- 2:整数部分(数字序列)
- 3:小数部分(有整数的小数点后数字)
- 4:小数部分(无整数的小数点后数字,如
.123
) - 5:指数符号(e/E)
- 6:指数部分的符号位(如
123e+4
中的+
) - 7:指数部分的整数
- 8:结尾空格
2. 转移表结构
vector<unordered_map<char, int>> states = { ... };
- 外层
vector
索引表示当前状态(0-8) - 内层
unordered_map
存储当前状态接受的字符类型及其对应的下一状态 - 字符类型包括:
'd'
:数字(0-9)'s'
:符号(+/-)'e'
:指数符号(e/E)'.'
:小数点' '
:空格
三、状态转移规则详解
1. 初始状态(0)
{{' ', 0}, {'s', 1}, {'d', 2}, {'.', 4}}
- 空格 → 保持初始状态(处理前导空格)
- 符号 → 进入符号位状态(如
+123
) - 数字 → 进入整数部分(如
123
) - 小数点 → 进入无整数的小数部分(如
.123
)
2. 符号位状态(1)
{{'d', 2}, {'.', 4}}
- 数字 → 进入整数部分(如
+123
) - 小数点 → 进入无整数的小数部分(如
-.123
)
3. 整数部分(2)
{{'d', 2}, {'.', 3}, {'e', 5}, {' ', 8}}
- 数字 → 保持整数部分(如
123
) - 小数点 → 进入有整数的小数部分(如
123.45
) - 指数符号 → 进入指数符号状态(如
123e4
) - 空格 → 进入结尾空格状态(如
123
)
4. 小数部分(3)
{{'d', 3}, {'e', 5}, {' ', 8}}
- 数字 → 保持小数部分(如
1.23
) - 指数符号 → 进入指数符号状态(如
1.23e4
) - 空格 → 进入结尾空格状态(如
1.23
)
5. 无整数的小数部分(4)
{{'d', 3}}
- 数字 → 进入有整数的小数部分(如
.123
变为0.123
)
6. 指数符号(5)
{{'s', 6}, {'d', 7}}
- 符号 → 进入指数符号位(如
123e+4
) - 数字 → 进入指数整数部分(如
123e4
)
7. 指数符号位(6)
{{'d', 7}}
- 数字 → 进入指数整数部分(如
123e+4
)
8. 指数整数部分(7)
{{'d', 7}, {' ', 8}}
- 数字 → 保持指数部分(如
123e4
) - 空格 → 进入结尾空格状态(如
123e4
)
9. 结尾空格(8)
{{' ', 8}}
- 空格 → 保持结尾空格状态(处理 trailing 空格)
四、字符类型映射
char type;
if (isdigit(c)) type = 'd';
else if (c == '+' || c == '-') type = 's';
else if (c == 'e' || c == 'E') type = 'e';
else if (c == '.') type = '.';
else if (c == ' ') type = ' ';
else return false; // 非法字符
- 将输入字符映射为5种类型之一
- 非法字符(如字母、其他符号)直接判定为无效
五、主验证逻辑
int currentState = 0;
for (char c : s) {// 字符类型映射...if (states[currentState].find(type) == states[currentState].end()) {return false; // 无法转移到下一个状态}currentState = states[currentState][type];
}// 最终有效状态:2(整数)、3(小数)、7(指数)、8(结尾空格)
return currentState == 2 || currentState == 3 || currentState == 7 || currentState == 8;
- 流程:
- 从初始状态(0)开始
- 遍历每个字符,映射为类型
type
- 检查当前状态是否接受该类型:
- 若接受,转移到下一状态
- 若不接受,返回
false
- 遍历结束后,检查最终状态是否为有效接受状态
六、接受状态说明
有效数字的最终状态必须是:
- 2:整数部分(如
"123"
) - 3:小数部分(如
"1.23"
、"123."
、".123"
) - 7:指数部分(如
"123e4"
、"1.23e-4"
) - 8:结尾空格(如
" 123 "
、"123e4 "
)
七、示例验证
1. 合法数字
"123"
:0 → 2 → 2 → 2(最终状态2,有效)"+1.23"
:0 → 1 → 2 → 3 → 3 → 3(最终状态3,有效)" 123e-4 "
:0 → 0 → 2 → 2 → 2 → 5 → 6 → 7 → 8 → 8(最终状态8,有效)
2. 非法数字
"123."
:0 → 2 → 2 → 2 → 3(最终状态3,有效,但实际应为无效,此处代码存在漏洞)"e123"
:0 → 5(无法继续转移,无效)"123e"
:0 → 2 → 2 → 2 → 5(无法继续转移,无效)
八、代码优化建议
- 修复小数点问题:当前代码允许
"123."
为有效,需调整状态3的定义 - 使用更安全的类型:用枚举替代状态数字,提高可读性
- 预计算字符类型映射:避免每次循环都进行条件判断
- 添加测试用例:覆盖所有边界情况(如
"123e"
、".e123"
等)
九、总结
该代码通过DFA实现了有效数字的验证,将复杂的语法规则转化为清晰的状态转移表。虽然存在一些边界处理问题,但核心思路正确,适用于大多数常见场景。
leetcode 官方解答:
class Solution {
public:enum State {STATE_INITIAL,STATE_INT_SIGN,STATE_INTEGER,STATE_POINT,STATE_POINT_WITHOUT_INT,STATE_FRACTION,STATE_EXP,STATE_EXP_SIGN,STATE_EXP_NUMBER,STATE_END};enum CharType {CHAR_NUMBER,CHAR_EXP,CHAR_POINT,CHAR_SIGN,CHAR_ILLEGAL};CharType toCharType(char ch) {if (ch >= '0' && ch <= '9') {return CHAR_NUMBER;} else if (ch == 'e' || ch == 'E') {return CHAR_EXP;} else if (ch == '.') {return CHAR_POINT;} else if (ch == '+' || ch == '-') {return CHAR_SIGN;} else {return CHAR_ILLEGAL;}}bool isNumber(string s) {unordered_map<State, unordered_map<CharType, State>> transfer{{STATE_INITIAL, {{CHAR_NUMBER, STATE_INTEGER},{CHAR_POINT, STATE_POINT_WITHOUT_INT},{CHAR_SIGN, STATE_INT_SIGN}}}, {STATE_INT_SIGN, {{CHAR_NUMBER, STATE_INTEGER},{CHAR_POINT, STATE_POINT_WITHOUT_INT}}}, {STATE_INTEGER, {{CHAR_NUMBER, STATE_INTEGER},{CHAR_EXP, STATE_EXP},{CHAR_POINT, STATE_POINT}}}, {STATE_POINT, {{CHAR_NUMBER, STATE_FRACTION},{CHAR_EXP, STATE_EXP}}}, {STATE_POINT_WITHOUT_INT, {{CHAR_NUMBER, STATE_FRACTION}}}, {STATE_FRACTION,{{CHAR_NUMBER, STATE_FRACTION},{CHAR_EXP, STATE_EXP}}}, {STATE_EXP,{{CHAR_NUMBER, STATE_EXP_NUMBER},{CHAR_SIGN, STATE_EXP_SIGN}}}, {STATE_EXP_SIGN, {{CHAR_NUMBER, STATE_EXP_NUMBER}}}, {STATE_EXP_NUMBER, {{CHAR_NUMBER, STATE_EXP_NUMBER}}}};int len = s.length();State st = STATE_INITIAL;for (int i = 0; i < len; i++) {CharType typ = toCharType(s[i]);if (transfer[st].find(typ) == transfer[st].end()) {return false;} else {st = transfer[st][typ];}}return st == STATE_INTEGER || st == STATE_POINT || st == STATE_FRACTION || st == STATE_EXP_NUMBER || st == STATE_END;}
};
代码解析:使用确定有限状态自动机验证有效数字
这段代码实现了LeetCode 65题「有效数字」的判断,采用了确定有限状态自动机(DFA)的思路。下面从整体到细节逐步解析:
一、整体解决方案概述
该解决方案通过以下步骤验证字符串是否为有效数字:
- 定义状态:将数字字符串的解析过程划分为不同阶段(状态)
- 定义字符类型:将输入字符分类为数字、指数符号等类型
- 构建状态转移表:定义每个状态在不同字符类型下的转移规则
- 状态转移遍历:从初始状态开始,按规则转移并判断最终状态
二、枚举类型定义
1. 状态枚举 (State)
enum State {STATE_INITIAL, // 初始状态(允许前导空格,但代码中未处理空格)STATE_INT_SIGN, // 整数符号位(+/-)STATE_INTEGER, // 整数部分(数字序列)STATE_POINT, // 小数点(左侧有整数)STATE_POINT_WITHOUT_INT, // 小数点(左侧无整数)STATE_FRACTION, // 小数部分(小数点后的数字)STATE_EXP, // 指数符号(e/E)STATE_EXP_SIGN, // 指数符号后的符号位(+/-)STATE_EXP_NUMBER, // 指数部分的整数STATE_END // 结束状态(示例中未充分使用)
};
- 每个状态代表当前解析到数字字符串的哪个阶段
- 例如:
STATE_POINT
表示已解析完整数部分,遇到小数点
2. 字符类型枚举 (CharType)
enum CharType {CHAR_NUMBER, // 数字(0-9)CHAR_EXP, // 指数符号(e/E)CHAR_POINT, // 小数点(.)CHAR_SIGN, // 符号位(+/-)CHAR_ILLEGAL // 非法字符
};
- 将输入字符分类,简化状态转移表的定义
- 例如:所有数字字符(‘0’-‘9’)都归为
CHAR_NUMBER
三、字符类型转换函数
CharType toCharType(char ch) {if (ch >= '0' && ch <= '9') {return CHAR_NUMBER;} else if (ch == 'e' || ch == 'E') {return CHAR_EXP;} else if (ch == '.') {return CHAR_POINT;} else if (ch == '+' || ch == '-') {return CHAR_SIGN;} else {return CHAR_ILLEGAL;}
}
- 功能:将输入字符映射到对应的
CharType
枚举值 - 逻辑:判断字符是否为数字、指数符号、小数点、符号位或非法字符
- 作用:使状态转移表只需关注字符类型,而非具体字符
四、状态转移表解析
unordered_map<State, unordered_map<CharType, State>> transfer{// 状态转移规则...
};
这是DFA的核心,定义了每个状态在不同字符类型下的转移目标。
1. 初始状态 (STATE_INITIAL)
{STATE_INITIAL, {{CHAR_NUMBER, STATE_INTEGER}, // 数字 → 整数部分{CHAR_POINT, STATE_POINT_WITHOUT_INT}, // 小数点 → 无整数的小数{CHAR_SIGN, STATE_INT_SIGN} // 符号 → 符号位}
},
- 初始状态可以接受数字、小数点或符号:
- 数字:进入整数部分解析
- 小数点:进入无整数的小数解析(如
.123
) - 符号:进入符号位解析(如
+123
)
2. 整数符号位 (STATE_INT_SIGN)
{STATE_INT_SIGN, {{CHAR_NUMBER, STATE_INTEGER}, // 数字 → 整数部分{CHAR_POINT, STATE_POINT_WITHOUT_INT} // 小数点 → 无整数的小数}
},
- 符号位后只能接数字或小数点:
- 例如:
+123
(符号→数字)、-.456
(符号→小数点)
- 例如:
3. 整数部分 (STATE_INTEGER)
{STATE_INTEGER, {{CHAR_NUMBER, STATE_INTEGER}, // 数字 → 保持整数部分{CHAR_EXP, STATE_EXP}, // 指数符号 → 指数解析{CHAR_POINT, STATE_POINT} // 小数点 → 有整数的小数}
},
- 整数部分后可接:
- 更多数字(保持整数部分)
- 指数符号(如
123e4
) - 小数点(如
123.45
)
4. 有整数的小数点 (STATE_POINT)
{STATE_POINT, {{CHAR_NUMBER, STATE_FRACTION}, // 数字 → 小数部分{CHAR_EXP, STATE_EXP} // 指数符号 → 指数解析}
},
- 小数点后可接:
- 数字(如
123.45
) - 指数符号(如
123.e4
)
- 数字(如
5. 无整数的小数点 (STATE_POINT_WITHOUT_INT)
{STATE_POINT_WITHOUT_INT, {{CHAR_NUMBER, STATE_FRACTION} // 数字 → 小数部分}
},
- 无整数的小数点后必须接数字(如
.123
) - 若小数点后无数字(如
.
),则转移失败
6. 小数部分 (STATE_FRACTION)
{STATE_FRACTION, {{CHAR_NUMBER, STATE_FRACTION}, // 数字 → 保持小数部分{CHAR_EXP, STATE_EXP} // 指数符号 → 指数解析}
},
- 小数部分后可接:
- 更多数字(如
1.234
) - 指数符号(如
1.23e4
)
- 更多数字(如
7. 指数符号 (STATE_EXP)
{STATE_EXP, {{CHAR_NUMBER, STATE_EXP_NUMBER}, // 数字 → 指数整数部分{CHAR_SIGN, STATE_EXP_SIGN} // 符号 → 指数符号位}
},
- 指数符号后可接:
- 数字(如
123e4
) - 符号(如
123e+4
、123e-4
)
- 数字(如
8. 指数符号位 (STATE_EXP_SIGN)
{STATE_EXP_SIGN, {{CHAR_NUMBER, STATE_EXP_NUMBER} // 数字 → 指数整数部分}
},
- 指数符号位后必须接数字(如
123e+4
) - 若符号后无数字(如
123e+
),则转移失败
9. 指数整数部分 (STATE_EXP_NUMBER)
{STATE_EXP_NUMBER, {{CHAR_NUMBER, STATE_EXP_NUMBER} // 数字 → 保持指数部分}
},
- 指数整数部分后可接更多数字(如
123e12
)
五、主验证逻辑
bool isNumber(string s) {int len = s.length();State st = STATE_INITIAL;for (int i = 0; i < len; i++) {CharType typ = toCharType(s[i]);if (transfer[st].find(typ) == transfer[st].end()) {return false; // 转移失败,非有效数字} else {st = transfer[st][typ]; // 更新状态}}// 最终状态必须是有效接受状态return st == STATE_INTEGER || st == STATE_POINT || st == STATE_FRACTION || st == STATE_EXP_NUMBER || st == STATE_END;
}
-
流程:
- 从初始状态
STATE_INITIAL
开始 - 逐个字符处理,转换为类型
CharType
- 根据当前状态和字符类型查找转移表
- 若转移规则不存在,直接返回
false
- 处理完所有字符后,检查最终状态是否为接受状态
- 从初始状态
-
接受状态:
STATE_INTEGER
:以整数结尾(如123
)STATE_POINT
:以有整数的小数点结尾(如123.
)STATE_FRACTION
:以小数结尾(如1.23
)STATE_EXP_NUMBER
:以指数部分结尾(如123e4
)STATE_END
:(示例中未充分使用,可用于结尾空格等场景)
六、代码注意事项
- 空格处理:当前代码未处理前导/ trailing 空格,实际有效数字可能包含空格(如
" 123 "
) - 状态转移表效率:使用
unordered_map
实现转移表,查找效率为 O(1),但可优化为数组进一步提高性能 - 非法字符处理:遇到
CHAR_ILLEGAL
类型时直接判定为无效 - 边界情况覆盖:
- 整数:
"123"
- 小数:
"1.23"
、".456"
- 指数:
"123e4"
、"1.2e-3"
- 符号:
"+123"
、"-4.5"
- 整数:
七、总结
该解决方案通过DFA清晰地建模了有效数字的解析过程,每个状态对应数字字符串的一个解析阶段,状态转移表定义了合法的字符接续规则。这种方法将复杂的规则判断转化为状态机的状态转移,逻辑清晰且易于维护,是解决字符串验证问题的经典思路。