LeetCode-Book 精讲 LCR 138「有效数字」有限状态自动机DFA判定合法数值【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book本篇技术指南以 LeetCode-Book 仓库中 leetbook_ioa/docs/LCR 138. 有效数字.md 为主体骨架系统讲解如何用**有限状态自动机Deterministic Finite Automaton, DFA**判断一个字符串是否为合法数值。读者学完本文将掌握从「字符类型分类 → 状态定义 → 状态转移表 → 三语言实现」的完整建模流程并能直接看懂仓库中 Python / Java / C 三种语言的解题实现理解2e10、 .1 、1e等典型样例为何被正确判定。题目背景一道三端题源反复考察的经典题「有效数字」是字符串处理题中极其经典的题目在 LeetCode-Book 仓库中被多次收录本文主体文档所在的 Leetbook 部分leetbook_ioa/docs/LCR 138. 有效数字.md对应力扣 LCR 138笔面试精选集部分selected_coding_interview/docs/65. 有效数字.md对应 LeetCode 65剑指 Offer 部分sword_for_offer/docs/剑指 Offer 20. 表示数值的字符串.md对应《剑指 Offer 20》。三道题题面与判定规则完全一致解法通用。之所以反复出现是因为它覆盖面广要求同时处理前导/尾随空格、正负号、小数点、科学计数法指数部分e/E的任意组合且存在大量边界情况如.非法、.1合法、1e非法、1e-2合法。用朴素的条件分支逐 case 枚举极易出错而有限状态自动机能把所有合法形态统一收敛为一张状态转移表一行不漏、边界安全。核心思想为什么选有限状态自动机一个合法数值字符串可以被拆解为若干「片段」按固定顺序拼接而成例如[可选首尾空格] [可选正负号] 整数/小数部分 [可选 e/E [可选正负号] 整数指数] [可选尾随空格]每个片段之间具有严格的先后依赖e只能出现在数字之后、指数必须是整数、小数点最多出现一次等。这种「按顺序扫描、逐字符判定、状态随输入推进」的过程天然适合用自动机建模每个状态代表字符串扫描到当前位置时已经满足的合法前缀形态每个输入字符被归类为有限的字符类型数字、正负号、小数点、幂符号、空格状态 字符类型 → 下一个状态构成状态转移函数扫描结束后若停在合法结束状态集合中则判定为合法数值。相比正则表达式逐分支回溯DFA 只需从左到右线性扫描一遍时间复杂度 $O(N)$、空间复杂度 $O(1)$既高效又无回溯歧义。字符类型分类把任意字符归并为 5 类原文档规定扫描时把每个字符归入以下类型即代码中的转移表键key字符类型含义对应字符代码记号t空格前导 / 尾随空格 用字符本身数字十进制数字0–9ddigit正负号幂符号前或后的符号,-ssign小数点小数分隔符..用字符本身幂符号科学计数法指数标记e,Eeexponent其他非法字符其余任意字符?直接判定失败注意两个细节小数点与空格直接用字符本身作为类型记号e与E大小写均视为幂符号任何未覆盖的字符一律归为?一旦出现立即返回false。状态定义9 种状态刻画合法前缀按照从左到右的扫描顺序原文档定义了以下 9 种状态0为起始状态状态编号含义0开始的空格1幂符号前的正负号2小数点前的数字3小数点、小数点后的数字4当小数点前为空格时小数点、小数点后的数字5幂符号6幂符号后的正负号7幂符号后的数字8结尾的空格合法的结束状态只有 2、3、7、8即字符串最终停在「数字」状态 2/3/7或「尾随空格」状态 8上才算合法如果停在符号、孤立小数点、幂符号状态 1/4/5/6上则非法。例如会停在状态 1、.会停在状态 4均不合法。状态 4 是本题最易遗漏的坑当字符串以.5这种形式开头时小数点前既没有数字也没有符号需要单独为「点后数字」开一个状态承接保证.1、 .1 这类输入合法。状态转移表把合法形态压缩成一张哈希表原文档给出的核心数据结构是状态转移表statesstates[i]是一个哈希表键为字符类型值为转移目标状态。以 Python 版为例selected_coding_interview/codes/python/lc_65_valid_number.py 与本文主体文档完全一致class Solution: def validNumber(self, s: str) - bool: states [ { : 0, s: 1, d: 2, .: 4 }, # 0. start with blank { d: 2, .: 4 } , # 1. sign before e { d: 2, .: 3, e: 5, : 8 }, # 2. digit before dot { d: 3, e: 5, : 8 }, # 3. digit after dot { d: 3 }, # 4. digit after dot (‘blank’ before dot) { s: 6, d: 7 }, # 5. e { d: 7 }, # 6. sign after e { d: 7, : 8 }, # 7. digit after e { : 8 } # 8. end with blank ] p 0 # start with state 0 for c in s: if 0 c 9: t d # digit elif c in -: t s # sign elif c in eE: t e # e or E elif c in . : t c # dot, blank else: t ? # unknown if t not in states[p]: return False p states[p][t] return p in (2, 3, 7, 8)将这张表整理成可视化的「状态 × 字符类型」转移矩阵能更直观地看到哪些组合被禁止空位即非法转移状态 空格s符号d数字.小数点e幂符号0 开始空格0124—1 幂前符号——24—2 点前数字8—2353 点后数字8—3—54 空格后的小数点——3——5 幂符号—67——6 幂后符号——7——7 幂后数字8—7——8 结尾空格8————从表中可以读出的关键约束幂符号e只能出现在数字之后只有状态 2、3 能接收e转移至状态 5因此e3起始即遇e、.e1小数点后无数字直接遇e都会被拒绝指数必须是整数状态 5、6、7 均无小数点转移因此1e2.5非法小数点最多一次、位置受限只有状态 0、1、2 能接收.点后必须跟随数字状态 3 或 4 只能转移至 3因此1.、.、.非法而1.0、.5合法符号只在两处出现幂符号前状态 0→1或幂符号后状态 5→6因此-1、1e-2这类多符号输入会被拒绝空格只在首尾状态 0 与状态 8 构成「前导空格链」与「尾随空格链」一旦进入状态 8 后只允许继续读空格因此1 2会被拒绝。算法流程初始化 → 逐字符转移 → 判定终态原文档将算法归纳为三步初始化构建状态转移表states并把当前状态指针p置为起始状态p 0。状态转移循环遍历字符串s的每个字符c记录字符类型t数字记d正负号记se/E记e.或空格用字符本身其余记?终止条件若t不在states[p]中说明当前状态无法接收该字符直接返回false状态转移令p states[p][t]推进到下一状态。返回值循环结束后若p ∈ {2, 3, 7, 8}说明结尾合法返回true否则返回false。结合上述转移表可以手工推演几个代表性样例与三语言实现的行为完全一致输入状态轨迹结果2e100 →2(d) →5(e) →7(d) →7(d)✅ 停在 7 -90e3 0 →0( ) →1(s) →2(d) →2(d) →5(e) →7(d) →7(d) →8( ) →8( )✅ 停在 8 .1 0 →0( ) →4(.) →3(d) →8( ) →8( )✅ 停在 81e0 →2(d) →5(e)❌ 停在 5非终态e30 → 状态 0 无e转移❌ 中途拒绝1 20 →2(d) →8( ) → 状态 8 无d转移❌ 中途拒绝.0 →4(.)❌ 停在 4非终态仓库中的三语言实现同一张表三种载体原文档指出「Java 的状态转移表states使用Map[]数组存储」LeetCode-Book 仓库则进一步给出了三语言完整实现核心逻辑与 Python 版逐行对应Java 实现位于 selected_coding_interview/codes/java/lc_65_valid_number/lc_65_valid_number.java使用Map[]数组 匿名内部类初始化class Solution { public boolean isNumber(String s) { Map[] states { new HashMap() {{ put( , 0); put(s, 1); put(d, 2); put(., 4); }}, // 0. new HashMap() {{ put(d, 2); put(., 4); }}, // 1. new HashMap() {{ put(d, 2); put(., 3); put(e, 5); put( , 8); }}, // 2. new HashMap() {{ put(d, 3); put(e, 5); put( , 8); }}, // 3. new HashMap() {{ put(d, 3); }}, // 4. new HashMap() {{ put(s, 6); put(d, 7); }}, // 5. new HashMap() {{ put(d, 7); }}, // 6. new HashMap() {{ put(d, 7); put( , 8); }}, // 7. new HashMap() {{ put( , 8); }} // 8. }; int p 0; char t; for(char c : s.toCharArray()) { if(c 0 c 9) t d; else if(c || c -) t s; else if(c e || c E) t e; else if(c . || c ) t c; else t ?; if(!states[p].containsKey(t)) return false; p (int)states[p].get(t); } return p 2 || p 3 || p 7 || p 8; } }C 实现位于 selected_coding_interview/codes/cpp/lc_65_valid_number/lc_65_valid_number_s1.cpp使用vectorunordered_mapchar, int表达同一张表并用states[p].count(t)判断转移是否存在逻辑与 Python/Java 完全同构。剑指 Offer 版本位于 sword_for_offer/codes/python/sfo_20_a_string_representing_a_numeric_value_s1.py其 driver 代码直接给出了一个高价值测试样例s .1 带前导空格、以小数点开头、带尾随空格运行输出True。这个样例正好覆盖了最容易写错的状态 4 → 3 → 8 转移链可作为自测用例复用到任意语言实现上。三份代码的判型分支d/s/e/.与空格与终态判定2、3、7、8完全一致说明「一张转移表 一次线性扫描」的建模思路可以零成本地在主流语言间迁移。复杂度分析时间复杂度 $O(N)$其中 $N$ 为字符串s的长度。算法只需从左到右遍历一次每轮状态转移是哈希表查找耗时为 $O(1)$空间复杂度 $O(1)$状态转移表states是固定 9 个状态的常量大小指针p为单个变量额外空间与输入长度无关。这也是 DFA 解法相比「枚举所有合法形态 逐个正则匹配」的核心优势不引入任何回溯或额外存储最坏情况也只需完整读一遍字符串。小结从这道题提炼的通用建模方法论「有效数字」一题的价值不止于 AC 一道题。它示范了解决「字符串格式校验」类问题的标准三步法归类输入把所有可能的字符压缩成有限数量的字符类型本题为空格 / 数字 / 符号 / 小数点 / 幂符号 / 非法枚举合法前缀顺着语法从左到右枚举所有可能的合法前缀形态即为状态集合本题 9 态填表并线性扫描把「状态 × 字符类型 → 下一状态」的合法组合填入转移表非法组合留空最后校验终态。这套方法可以复用到诸如 IP 地址校验、版本号解析、日期格式校验等一切「有明确语法规则的字符串校验」场景。若想深入理解可对照阅读 LeetCode-Book 中的三份文档LCR 138、LeetCode 65、剑指 Offer 20以及对应的 Python、Java、C 源码自行推演更多边界样例如959440.94f、6e-1、99e2.5即可彻底吃透这张 9 态转移表。【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
LeetCode-Book 精讲 LCR 138「有效数字」：有限状态自动机（DFA）判定合法数值
LeetCode-Book 精讲 LCR 138「有效数字」有限状态自动机DFA判定合法数值【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book本篇技术指南以 LeetCode-Book 仓库中 leetbook_ioa/docs/LCR 138. 有效数字.md 为主体骨架系统讲解如何用**有限状态自动机Deterministic Finite Automaton, DFA**判断一个字符串是否为合法数值。读者学完本文将掌握从「字符类型分类 → 状态定义 → 状态转移表 → 三语言实现」的完整建模流程并能直接看懂仓库中 Python / Java / C 三种语言的解题实现理解2e10、 .1 、1e等典型样例为何被正确判定。题目背景一道三端题源反复考察的经典题「有效数字」是字符串处理题中极其经典的题目在 LeetCode-Book 仓库中被多次收录本文主体文档所在的 Leetbook 部分leetbook_ioa/docs/LCR 138. 有效数字.md对应力扣 LCR 138笔面试精选集部分selected_coding_interview/docs/65. 有效数字.md对应 LeetCode 65剑指 Offer 部分sword_for_offer/docs/剑指 Offer 20. 表示数值的字符串.md对应《剑指 Offer 20》。三道题题面与判定规则完全一致解法通用。之所以反复出现是因为它覆盖面广要求同时处理前导/尾随空格、正负号、小数点、科学计数法指数部分e/E的任意组合且存在大量边界情况如.非法、.1合法、1e非法、1e-2合法。用朴素的条件分支逐 case 枚举极易出错而有限状态自动机能把所有合法形态统一收敛为一张状态转移表一行不漏、边界安全。核心思想为什么选有限状态自动机一个合法数值字符串可以被拆解为若干「片段」按固定顺序拼接而成例如[可选首尾空格] [可选正负号] 整数/小数部分 [可选 e/E [可选正负号] 整数指数] [可选尾随空格]每个片段之间具有严格的先后依赖e只能出现在数字之后、指数必须是整数、小数点最多出现一次等。这种「按顺序扫描、逐字符判定、状态随输入推进」的过程天然适合用自动机建模每个状态代表字符串扫描到当前位置时已经满足的合法前缀形态每个输入字符被归类为有限的字符类型数字、正负号、小数点、幂符号、空格状态 字符类型 → 下一个状态构成状态转移函数扫描结束后若停在合法结束状态集合中则判定为合法数值。相比正则表达式逐分支回溯DFA 只需从左到右线性扫描一遍时间复杂度 $O(N)$、空间复杂度 $O(1)$既高效又无回溯歧义。字符类型分类把任意字符归并为 5 类原文档规定扫描时把每个字符归入以下类型即代码中的转移表键key字符类型含义对应字符代码记号t空格前导 / 尾随空格 用字符本身数字十进制数字0–9ddigit正负号幂符号前或后的符号,-ssign小数点小数分隔符..用字符本身幂符号科学计数法指数标记e,Eeexponent其他非法字符其余任意字符?直接判定失败注意两个细节小数点与空格直接用字符本身作为类型记号e与E大小写均视为幂符号任何未覆盖的字符一律归为?一旦出现立即返回false。状态定义9 种状态刻画合法前缀按照从左到右的扫描顺序原文档定义了以下 9 种状态0为起始状态状态编号含义0开始的空格1幂符号前的正负号2小数点前的数字3小数点、小数点后的数字4当小数点前为空格时小数点、小数点后的数字5幂符号6幂符号后的正负号7幂符号后的数字8结尾的空格合法的结束状态只有 2、3、7、8即字符串最终停在「数字」状态 2/3/7或「尾随空格」状态 8上才算合法如果停在符号、孤立小数点、幂符号状态 1/4/5/6上则非法。例如会停在状态 1、.会停在状态 4均不合法。状态 4 是本题最易遗漏的坑当字符串以.5这种形式开头时小数点前既没有数字也没有符号需要单独为「点后数字」开一个状态承接保证.1、 .1 这类输入合法。状态转移表把合法形态压缩成一张哈希表原文档给出的核心数据结构是状态转移表statesstates[i]是一个哈希表键为字符类型值为转移目标状态。以 Python 版为例selected_coding_interview/codes/python/lc_65_valid_number.py 与本文主体文档完全一致class Solution: def validNumber(self, s: str) - bool: states [ { : 0, s: 1, d: 2, .: 4 }, # 0. start with blank { d: 2, .: 4 } , # 1. sign before e { d: 2, .: 3, e: 5, : 8 }, # 2. digit before dot { d: 3, e: 5, : 8 }, # 3. digit after dot { d: 3 }, # 4. digit after dot (‘blank’ before dot) { s: 6, d: 7 }, # 5. e { d: 7 }, # 6. sign after e { d: 7, : 8 }, # 7. digit after e { : 8 } # 8. end with blank ] p 0 # start with state 0 for c in s: if 0 c 9: t d # digit elif c in -: t s # sign elif c in eE: t e # e or E elif c in . : t c # dot, blank else: t ? # unknown if t not in states[p]: return False p states[p][t] return p in (2, 3, 7, 8)将这张表整理成可视化的「状态 × 字符类型」转移矩阵能更直观地看到哪些组合被禁止空位即非法转移状态 空格s符号d数字.小数点e幂符号0 开始空格0124—1 幂前符号——24—2 点前数字8—2353 点后数字8—3—54 空格后的小数点——3——5 幂符号—67——6 幂后符号——7——7 幂后数字8—7——8 结尾空格8————从表中可以读出的关键约束幂符号e只能出现在数字之后只有状态 2、3 能接收e转移至状态 5因此e3起始即遇e、.e1小数点后无数字直接遇e都会被拒绝指数必须是整数状态 5、6、7 均无小数点转移因此1e2.5非法小数点最多一次、位置受限只有状态 0、1、2 能接收.点后必须跟随数字状态 3 或 4 只能转移至 3因此1.、.、.非法而1.0、.5合法符号只在两处出现幂符号前状态 0→1或幂符号后状态 5→6因此-1、1e-2这类多符号输入会被拒绝空格只在首尾状态 0 与状态 8 构成「前导空格链」与「尾随空格链」一旦进入状态 8 后只允许继续读空格因此1 2会被拒绝。算法流程初始化 → 逐字符转移 → 判定终态原文档将算法归纳为三步初始化构建状态转移表states并把当前状态指针p置为起始状态p 0。状态转移循环遍历字符串s的每个字符c记录字符类型t数字记d正负号记se/E记e.或空格用字符本身其余记?终止条件若t不在states[p]中说明当前状态无法接收该字符直接返回false状态转移令p states[p][t]推进到下一状态。返回值循环结束后若p ∈ {2, 3, 7, 8}说明结尾合法返回true否则返回false。结合上述转移表可以手工推演几个代表性样例与三语言实现的行为完全一致输入状态轨迹结果2e100 →2(d) →5(e) →7(d) →7(d)✅ 停在 7 -90e3 0 →0( ) →1(s) →2(d) →2(d) →5(e) →7(d) →7(d) →8( ) →8( )✅ 停在 8 .1 0 →0( ) →4(.) →3(d) →8( ) →8( )✅ 停在 81e0 →2(d) →5(e)❌ 停在 5非终态e30 → 状态 0 无e转移❌ 中途拒绝1 20 →2(d) →8( ) → 状态 8 无d转移❌ 中途拒绝.0 →4(.)❌ 停在 4非终态仓库中的三语言实现同一张表三种载体原文档指出「Java 的状态转移表states使用Map[]数组存储」LeetCode-Book 仓库则进一步给出了三语言完整实现核心逻辑与 Python 版逐行对应Java 实现位于 selected_coding_interview/codes/java/lc_65_valid_number/lc_65_valid_number.java使用Map[]数组 匿名内部类初始化class Solution { public boolean isNumber(String s) { Map[] states { new HashMap() {{ put( , 0); put(s, 1); put(d, 2); put(., 4); }}, // 0. new HashMap() {{ put(d, 2); put(., 4); }}, // 1. new HashMap() {{ put(d, 2); put(., 3); put(e, 5); put( , 8); }}, // 2. new HashMap() {{ put(d, 3); put(e, 5); put( , 8); }}, // 3. new HashMap() {{ put(d, 3); }}, // 4. new HashMap() {{ put(s, 6); put(d, 7); }}, // 5. new HashMap() {{ put(d, 7); }}, // 6. new HashMap() {{ put(d, 7); put( , 8); }}, // 7. new HashMap() {{ put( , 8); }} // 8. }; int p 0; char t; for(char c : s.toCharArray()) { if(c 0 c 9) t d; else if(c || c -) t s; else if(c e || c E) t e; else if(c . || c ) t c; else t ?; if(!states[p].containsKey(t)) return false; p (int)states[p].get(t); } return p 2 || p 3 || p 7 || p 8; } }C 实现位于 selected_coding_interview/codes/cpp/lc_65_valid_number/lc_65_valid_number_s1.cpp使用vectorunordered_mapchar, int表达同一张表并用states[p].count(t)判断转移是否存在逻辑与 Python/Java 完全同构。剑指 Offer 版本位于 sword_for_offer/codes/python/sfo_20_a_string_representing_a_numeric_value_s1.py其 driver 代码直接给出了一个高价值测试样例s .1 带前导空格、以小数点开头、带尾随空格运行输出True。这个样例正好覆盖了最容易写错的状态 4 → 3 → 8 转移链可作为自测用例复用到任意语言实现上。三份代码的判型分支d/s/e/.与空格与终态判定2、3、7、8完全一致说明「一张转移表 一次线性扫描」的建模思路可以零成本地在主流语言间迁移。复杂度分析时间复杂度 $O(N)$其中 $N$ 为字符串s的长度。算法只需从左到右遍历一次每轮状态转移是哈希表查找耗时为 $O(1)$空间复杂度 $O(1)$状态转移表states是固定 9 个状态的常量大小指针p为单个变量额外空间与输入长度无关。这也是 DFA 解法相比「枚举所有合法形态 逐个正则匹配」的核心优势不引入任何回溯或额外存储最坏情况也只需完整读一遍字符串。小结从这道题提炼的通用建模方法论「有效数字」一题的价值不止于 AC 一道题。它示范了解决「字符串格式校验」类问题的标准三步法归类输入把所有可能的字符压缩成有限数量的字符类型本题为空格 / 数字 / 符号 / 小数点 / 幂符号 / 非法枚举合法前缀顺着语法从左到右枚举所有可能的合法前缀形态即为状态集合本题 9 态填表并线性扫描把「状态 × 字符类型 → 下一状态」的合法组合填入转移表非法组合留空最后校验终态。这套方法可以复用到诸如 IP 地址校验、版本号解析、日期格式校验等一切「有明确语法规则的字符串校验」场景。若想深入理解可对照阅读 LeetCode-Book 中的三份文档LCR 138、LeetCode 65、剑指 Offer 20以及对应的 Python、Java、C 源码自行推演更多边界样例如959440.94f、6e-1、99e2.5即可彻底吃透这张 9 态转移表。【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考