LeetCode 423. 从英文中重建数字

约 5 分钟
文章信息 6 个分类 3 个标签
分类
LeetCode CodeTop 中等 未解决 2-5 字节
标签
字符串 哈希表 数学

题目描述

✅ 423. 从英文中重建数字

image-20260928224119863

题意分析

输入由若干个数字零到九的英文单词中的全部字母打乱组成，恢复这些数字，并按从小到大的顺序返回数字字符串。每个数字可以出现多次，输出也要保留对应次数。

字母已经整体打乱，不能按连续子串寻找单词，也不需要恢复原来数字的排列顺序。题目保证输入有效，因此可以利用各英文单词的字母组成直接推导数量；结果允许以零开头，应当作为字符串返回。

解法：唯一字母计数

核心思路

[!blue]

先统计每个字母的出现次数。虽然大部分字母被多个数字单词共享，但有五个字母只属于一个数字：z 只在 zero，w 只在 two，u 只在 four，x 只在 six，g 只在 eight。它们在对应单词中又都只出现一次，所以能直接确定零、二、四、六、八的数量。

确定一部分数字后，共享字母也可以继续使用。h 由 three 和 eight 贡献，扣掉八的数量就得到三；f 由 four 和 five 贡献，扣掉四就得到五；s 由 six 和 seven 贡献，扣掉六就得到七。

字母 o 出现在 zero、one、two、four 中，扣掉已经确定的零、二、四，就是一的数量。字母 i 出现在 five、six、eight、nine 中，扣掉五、六、八，才能得到九。

这是一条按依赖关系求解的计数链。原字母频次表始终保留总次数，已知贡献通过公式相减，不需要真的把整个单词逐字删除；但九必须在五确定之后计算，否则会把五贡献的字母也算进去。输入有效保证这些推导得到的数量非负且能够完整还原。

求解顺序服务于消除歧义，输出顺序服务于题目的升序要求，两者不同。所有数量求完后，再从数字零枚举到九，按各自数量追加数字字符，得到最终字符串。

解题步骤

  1. 扫描字符串，统计二十六个小写字母的频次。
  2. 用唯一字母直接得到零、二、四、六、八的数量。
  3. 从共享字母中减去已知贡献，依次求出三、五、七、一、九。
  4. 按零到九的顺序，将每个数字重复输出对应次数。

代码实现

class Solution {
    // z,w,u,x,g 分别只出现在 zero,two,four,six,eight 中，可以先确定这些数字数量。
    public String originalDigits(String s) {
        int[] count = new int[26];

        for (char c : s.toCharArray()) {
            count[c - 'a']++;
        }

        int[] nums = new int[10];

        nums[0] = count['z' - 'a'];
        nums[2] = count['w' - 'a'];
        nums[4] = count['u' - 'a'];
        nums[6] = count['x' - 'a'];
        nums[8] = count['g' - 'a'];
        // 唯一字母对应数字已确定，再扣掉共享字母的已知贡献
        nums[3] = count['h' - 'a'] - nums[8];
        nums[5] = count['f' - 'a'] - nums[4];
        nums[7] = count['s' - 'a'] - nums[6];
        nums[1] = count['o' - 'a'] - nums[0] - nums[2] - nums[4];
        // 九还依赖刚求出的五，不能提前计算
        nums[9] = count['i' - 'a'] - nums[5] - nums[6] - nums[8];

        StringBuilder builder = new StringBuilder(s.length());

        for (int i = 0; i < 10; i++) {
            for (int j = 0; j < nums[i]; j++) {
                builder.append(i);
            }
        }

        return builder.toString();
    }
}

func originalDigits(s string) string {
    // z,w,u,x,g 分别只出现在 zero,two,four,six,eight 中，可以先确定这些数字数量。
    count := make([]int, 26)
    for i := 0; i < len(s); i++ {
        count[s[i]-'a']++
    }

    nums := make([]int, 10)
    nums[0] = count['z'-'a']
    nums[2] = count['w'-'a']
    nums[4] = count['u'-'a']
    nums[6] = count['x'-'a']
    nums[8] = count['g'-'a']
    // 唯一字母对应数字已确定，再扣掉共享字母的已知贡献
    nums[3] = count['h'-'a'] - nums[8]
    nums[5] = count['f'-'a'] - nums[4]
    nums[7] = count['s'-'a'] - nums[6]
    nums[1] = count['o'-'a'] - nums[0] - nums[2] - nums[4]
    // 九还依赖刚求出的五，不能提前计算
    nums[9] = count['i'-'a'] - nums[5] - nums[6] - nums[8]

    builder := make([]byte, 0, len(s))
    for i := 0; i < 10; i++ {
        for j := 0; j < nums[i]; j++ {
            builder = append(builder, byte('0'+i))
        }
    }

    return string(builder)
}

复杂度分析

  • 时间复杂度：$O(n)$，n 为输入字母数。扫描和结果构造都是线性，十个数字的公式推导为常数工作。
  • 空间复杂度：$O(n)$，当前实现的字符处理与结果构造缓冲为线性空间；两个频次数组本身大小固定。

关键点总结

[!green]

  • 先用唯一字母确定部分数字，再从共享字母中扣除已知贡献。
  • 公式有依赖顺序，原频次表不变，不能一边整体减字母又重复使用这些扣减公式。
  • 数量全部确定后才按升序输出，重复数字与前导零都保留。

易错点总结

[!yellow]

  • 九的数量忘记减去八或五贡献的 i，会凭空增加数字九。
  • 五尚未确定就计算九，使用了未完成的依赖，导致计数错误。
  • 按数字被推导出来的先后顺序输出，会破坏从小到大的要求。
  • 先把已知单词从频次中扣除，再套用同样的减法公式，会把贡献重复扣掉。
  • 将结果转换成整数，会丢掉应当保留的前导零，也没有必要。
  • Java 把数字值直接强转为字符，得到的是字符编码而非十进制数字；当前代码使用 append(int) 输出其数字表示。

相似题目

题目 难度 关联与区别
383. 赎金信 简单 同样按字母频次消耗需求，本题利用某些数字单词的唯一字母确定数量，再扣除已使用字符。
869. 重新排序得到 2 的幂 中等 原题枚举候选数并比较数码频次，本题从混合字母频次中逐步还原多个数字单词。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/15132135
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！