LeetCode 剑指 Offer 20. 表示数值的字符串

约 11 分钟
文章信息 9 个分类 1 个标签
分类
LeetCode CodeTop 中等 未解决 2-5 字节跳动 快手 剑指 Offer 剑指 Offer（第 2 版）
标签
字符串
目录

题目描述

✅ 剑指 Offer 20. 表示数值的字符串

image-20241107205156269

题意分析

判断一个字符串是否表示一个合法的数值。这类题的难点从来不在算法，而在把规则拆清楚——没拆干净就一定会漏用例。

把题目描述翻译成结构，一个合法数值由三段组成：可选的符号、必需的小数部分、可选的指数部分；整体前后允许有空格，中间不允许。

小数部分有三种合法形态：纯整数如 123；带小数点且两侧都有数字如 1.5；带小数点但只有一侧有数字，如 .5 和 3.。这两种「半边」形式都是合法的，是最容易判错的地方；但小数点两侧都没数字的 . 则非法。

指数部分由 e 或 E 引导，后面跟一个可带符号的整数——注意这里必须是整数，1e2.5 非法；而且 e 前面必须已经出现过数字（e9、.e3 都非法），e 后面也必须跟上至少一个数字（1e、1e+ 都非法）。

符号只能出现在两个位置：整个字符串的开头，或者紧跟在 e/E 后面。其余任何位置的 +、- 都非法。

空格只允许出现在首尾，中间任何位置的空格都会让字符串非法，比如 1 2。

字符串长度约束很小，$O(n)$ 一趟扫描绰绰有余；真正被考察的是能否把规则完整地枚举出来并落成互不重叠的分支，这也是它作为「面试八股」的价值所在。

边界包括：空串、全是空格的串、只有一个 .、只有一个符号、以 e 结尾。这些都必须返回 false。

解法：一次扫描

核心思路

一种做法是写正则，一行搞定。但面试里这等于交白卷——考点就是规则的拆解与状态维护，用正则等于把它整个绕开。另一种做法是画出完整的有限状态机，按状态转移表逐字符推进；它最严谨，但白板上画九个状态的转移表既费时又容易抄错。

中间路线是：不显式建状态机，而是用几个布尔标志把「到目前为止看到了什么」记下来，每读一个字符就用这些标志判断它出现在这里是否合法。这样代码短、可读、也足够严谨，是面试中性价比最高的写法。

需要哪些标志？把上面的规则倒过来看，判断当前字符合法与否，只依赖三类历史信息：

seenDigit —— 是否已经出现过数字。它决定 e 能否出现（e 前必须有数字），也决定整个串是否可能合法（一个数字都没有必然非法）。

seenDot —— 是否已经出现过小数点。它保证小数点最多出现一次。

seenExp —— 是否已经出现过 e/E。它保证指数最多出现一次，同时也用来禁止指数之后再出现小数点。

还差一个：e 后面必须至少有一个数字。这条无法只靠上面三个标志判断，因为它是一个「未来必须发生」的约束。技巧是用 digitAfterExp 这个标志把它转成「当前是否已满足」：初值设为 true（还没有指数，这条约束空成立），一旦遇到 e 就置为 false（欠下一笔债），此后只要再读到任何数字就重新置为 true（债还清）。扫描结束时它若仍是 false，说明 e 后面没跟数字。

于是循环不变量是：每处理完一个字符，四个标志准确刻画了已扫描前缀的状态，且到此为止的前缀不违反任何规则。任何一次判断发现违规就立刻返回 false，不必继续扫描——这也是「一次扫描」写法能保持简洁的原因。

循环结束后返回 seenDigit && digitAfterExp：前者保证串里确实有数字（挡掉 .、+、e 这类无数字的串），后者保证指数后面跟了数字（挡掉 1e、1e+）。这两个条件合起来，就是所有「必须发生但可能没发生」的约束的总检查点。

解题步骤

  • 先 trim 掉首尾空格，再判空：题目允许首尾空格，去掉后主循环就能把任何空格都当作非法字符处理，规则少一条分支。去空格后若长度为 0（原串是空串或全空格），直接返回 false。
  • 四个标志的初值：seenDigit、seenDot、seenExp 都是 false（什么都还没看到）；digitAfterExp 初值是 true 而不是 false——它的语义是「指数后数字的约束当前是否满足」，还没有指数时这条约束空成立。这个反直觉的初值是全题最需要想清楚的一处。
  • 遇到数字：置 seenDigit = true；若已经进入指数部分（seenExp 为真），同时把 digitAfterExp 置回 true 还清欠债。数字在任何位置都合法，所以这一支没有任何返回 false 的分支。
  • 遇到 .：若 seenDot 已为真（第二个小数点）或 seenExp 已为真（指数部分不能有小数点），返回 false；否则置 seenDot = true。注意这里不检查小数点两侧是否有数字——那由最终的 seenDigit 兜底，这样 .5 和 3. 才能自然通过，而 . 会因为 seenDigit 为假被挡掉。
  • 遇到 e 或 E：若 seenExp 已为真（第二个指数）或 seenDigit 为假（指数前没有数字），返回 false；否则置 seenExp = true，并把 digitAfterExp 置为 false 记下这笔债。
  • 遇到 + 或 -：只有当它在开头（i == 0）或紧跟在 e/E 之后时才合法，否则返回 false。判断写成「不满足这两种情况就返回 false」，比正向列举更不易漏。这一支不修改任何标志，因为符号不携带「看到过数字」之类的信息。
  • 其余任何字符（字母、空格、逗号等）：直接返回 false。把这一支放在最后作为兜底，能保证规则的枚举是完备的。
  • 返回 seenDigit && digitAfterExp：两个「必须发生」的约束在这里统一结算。

以 s = "-1E-16" 走一遍（合法，应返回 true）。

初始：seenDigit = false、seenDot = false、seenExp = false、digitAfterExp = true。

i = 0，字符 -：走符号分支，i == 0 成立，合法，标志不变。

i = 1，字符 1：数字分支，seenDigit = true；seenExp 为假，不动 digitAfterExp。

i = 2，字符 E：指数分支，seenExp 为假且 seenDigit 为真，通过；置 seenExp = true、digitAfterExp = false（欠债）。

i = 3，字符 -：符号分支，i != 0，但前一个字符是 E，合法。

i = 4，字符 1：数字分支，seenDigit 已是真；seenExp 为真，所以 digitAfterExp = true（还债）。

i = 5，字符 6：同上，标志不变。

循环结束，返回 true && true = true，正确。

再看三个反例。"1e"：读完 e 后 digitAfterExp 被置为 false，之后没有任何数字，最终返回 false。"."：小数点分支正常通过并置 seenDot = true，但循环结束时 seenDigit 仍为 false，返回 false。"1 2"：中间的空格在 trim 后依然存在，落进兜底分支直接返回 false。

最后体会 digitAfterExp 初值的必要性：如果把它初始化成 false，"123" 这种根本没有指数的串会在最终检查处被判为非法——这正是「未来约束」必须用「当前已满足」来表达时最典型的陷阱。

代码实现

class Solution {
    // 记录是否出现过数字、点号、指数以及指数后的数字。
    public boolean isNumber(String s) {
        if (s == null) {
            return false;
        }

        s = s.trim();
        if (s.length() == 0) {
            return false;
        }

        boolean seenDigit = false;
        boolean seenDot = false;
        boolean seenExp = false;
        boolean digitAfterExp = true;

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);

            if (c >= '0' && c <= '9') {
                seenDigit = true;
                if (seenExp) {
                    digitAfterExp = true;
                }
            } else if (c == '.') {
                if (seenDot || seenExp) {
                    return false;
                }
                seenDot = true;
            } else if (c == 'e' || c == 'E') {
                if (seenExp || !seenDigit) {
                    return false;
                }
                seenExp = true;
                digitAfterExp = false;
            } else if (c == '+' || c == '-') {
                if (i != 0 && s.charAt(i - 1) != 'e' && s.charAt(i - 1) != 'E') {
                    return false;
                }
            } else {
                return false;
            }
        }

        return seenDigit && digitAfterExp;
    }
}

func isNumber(s string) bool {
    // 记录是否出现过数字、点号、指数以及指数后的数字。
    s = strings.TrimSpace(s)
    if len(s) == 0 {
        return false
    }

    seenDigit := false
    seenDot := false
    seenExp := false
    digitAfterExp := true

    for i := 0; i < len(s); i++ {
        c := s[i]

        if c >= '0' && c <= '9' {
            seenDigit = true
            if seenExp {
                digitAfterExp = true
            }
        } else if c == '.' {
            if seenDot || seenExp {
                return false
            }
            seenDot = true
        } else if c == 'e' || c == 'E' {
            if seenExp || !seenDigit {
                return false
            }
            seenExp = true
            digitAfterExp = false
        } else if c == '+' || c == '-' {
            if i != 0 && s[i-1] != 'e' && s[i-1] != 'E' {
                return false
            }
        } else {
            return false
        }
    }

    return seenDigit && digitAfterExp
}

复杂度分析

  • 时间复杂度：$O(n)$，其中 $n$ 是字符串长度。trim 一趟、主循环一趟，每个字符只做常数次比较与标志赋值，且一旦发现违规立即返回，不存在回退或重扫。
  • 空间复杂度：$O(1)$，只用了四个布尔标志和一个循环下标，与串长无关。Java 的 trim() 会新建一个字符串，若严格计较则是 $O(n)$，可以改成维护左右两个下标来避免。

关键点总结

  • 这类「合法性判定」题的胜负手是先把规则完整枚举成互不重叠的分支，再写代码。面试时先花一分钟口头列出「符号 / 小数部分 / 指数部分」三段结构和各自的约束，比直接动手更能拿分。
  • 「未来必须发生」的约束要转成「当前是否已满足」的标志，并把初值设成 true（约束尚未被触发时空成立）。digitAfterExp 就是这个技巧的教科书例子，它同样适用于「左括号必须被闭合」「引号必须成对」等场景。
  • 不要在小数点处急着检查两侧有无数字，把这类全局性约束统一推迟到循环结束后结算（这里是 seenDigit），能让 .5 与 3. 这类半边形式自然通过，分支数量也少得多。
  • 分支的兜底 else return false 必须存在：显式列举合法字符、其余一律非法，比反过来列举非法字符更不容易漏（谁能列全所有非法字符？）。
  • 面试中若被追问更严谨的写法，可以提有限状态机版本（约九个状态），并说明布尔标志法本质上是它的压缩形式——能指出两者的关系比只会一种写法更好。
  • 用正则一行解决在工程里是对的，在面试里是错的；如果面试官允许，也要主动补一句手写版本的思路。

易错点总结

  • digitAfterExp 初值写成 false："123" 这种没有指数的串在最终检查处被判非法，所有不含 e 的合法数字全军覆没。
  • 忘记在指数后遇到数字时把 digitAfterExp 置回 true："1e5" 会返回 false，只要带指数就必错。
  • e 分支不检查 seenDigit："e9"、".e3" 会被判成合法，而它们都非法——指数前必须有数字。
  • . 分支不检查 seenExp："1e2.5" 会被判成合法，但指数部分必须是整数。
  • 符号只允许出现在 i == 0："1e+5" 会返回 false，漏掉了紧跟 e 的符号这一合法位置。
  • 符号分支写成「在开头或前一位是 e 就置某个标志」却忘记非法情况直接返回："1+2" 会被放行，返回 true，而它显然非法。
  • 在小数点处直接要求两侧有数字：".5" 或 "3." 会被误判为非法，而这两者都是合法数值。
  • 没有兜底的 else return false："1a2" 里的 a 不匹配任何分支而被静默跳过，返回 true。
  • 不做 trim 就进主循环：" 1" 里的前导空格落进兜底分支返回 false，而题目允许首尾空格。
  • trim 后忘记判空：原串是 " " 时 trim 结果为空串，循环一次不进，seenDigit 为假仍能正确返回 false；但若把最终返回写成 true 或只检查 digitAfterExp，空串就会被判成合法。
  • 用 Character.isDigit(c) 而不写范围判断：它对全角数字 '１' 和其他 Unicode 数字也返回 true，"１" 会被误判为合法；本题应严格限定 '0' 到 '9'。
  • 直接 try { Double.parseDouble(s); return true; }："1d"、"0x1A"、"Infinity"、"NaN" 都能被 Java 解析成功，但按题目规则全部非法。

相似题目

题目 难度 考察点
65. 有效数字 困难 与本题同题，规则完全一致，可直接套用
8. 字符串转换整数 (atoi) 中等 不只判定还要求值，重点转向截断规则与 32 位溢出的处理
剑指 Offer 67. 把字符串转换成整数 中等 与 8 同题
468. 验证IP地址 中等 同为多规则合法性判定，需按分隔符切段后逐段校验长度、进制与前导零
20. 有效的括号 简单 合法性由嵌套结构决定，必须用栈而非几个布尔标志
678. 有效的括号字符串 中等 通配符让状态变成一个区间，用上下界双计数器代替单一标志
32. 最长有效括号 困难 不止判定还要求最长合法子串，需栈记录下标或用 DP
227. 基本计算器 II 中等 同样逐字符扫描并维护状态，但要边解析边按优先级求值