LeetCode 423. 从英文中重建数字
目录
题目描述
题意分析
输入是若干个英文数字单词（
zero到nine）的字母被完全打乱后拼在一起的字符串，要求还原出这些数字，并按升序输出成一个数字串。最强的约束信号是「顺序被打乱」和「保证输入有效」这两句。前者意味着字母的先后位置不携带任何信息，字符串实际退化成了一个字母的多重集，唯一可用的量就是每个字母出现了多少次；后者意味着不必考虑无解或残留字母，任何合法推导得到的计数都一定是非负且自洽的。
输出要求升序，进一步说明连「哪个单词在前」都不需要还原，只需要知道每个数字各出现了几次。
规模上字符串长度可达 $10^5$ 量级，所以输出拼接不能用反复复制的方式；字符集固定为 26 个小写字母，计数结构可以开成定长数组而不是哈希表。
边界包括：空串（返回空串）、同一个数字重复出现很多次、以及只有一种数字的输入。
解法：唯一字母计数
核心思路
最直接的想法是搜索：维护当前剩余的字母计数，每次尝试减去某个单词所需的字母，减得动就递归下去，减不动就回溯。这样确实能还原，但分支因子是 10，深度是单词个数，在长输入下完全不可接受，而且要额外证明解的唯一性才敢在第一次成功时返回。
瓶颈在于搜索把十个单词一视同仁，完全没有利用它们字母构成上的差异。
观察这十个单词的字母分布会发现一件事：有些字母只属于唯一一个单词。字母
z只出现在zero，w只出现在two，u只出现在four，x只出现在six，g只出现在eight。于是 0、2、4、6、8 的个数可以被这五个字母的计数直接读出来，不需要任何搜索。把这批数字的贡献扣掉之后，原本被共享的字母就变成了只含一个未知数的等式：
h出现在three和eight，eight已知，于是 3 的个数等于h的计数减去 8 的个数；同理f出现在four和five，s出现在six和seven，分别定出 5 和 7。最后o出现在zero、one、two、four中，除one外都已知，定出 1；i出现在five、six、eight、nine中，除nine外都已知，定出 9。因此本解法维持的不变量是：按「无共享字母的 0/2/4/6/8」→「只差一项的 3/5/7」→「依赖前两批的 1/9」这个顺序求解时，每一步待求数字所依赖的其他数字都已经被确定，整条消元链无环，一次线性扫描即可解完。
解题步骤
- 开一个长度 26 的计数数组，扫描字符串统计每个小写字母的出现次数。之所以用定长数组而不是哈希表，是因为字符集固定，数组的常数更小且不会有装箱开销。
- 用五个唯一字母直接定出第一批：
nums[0] = cnt['z']，nums[2] = cnt['w']，nums[4] = cnt['u']，nums[6] = cnt['x']，nums[8] = cnt['g']。每个单词里这些字母都恰好出现一次，所以计数就等于个数，不需要再除以任何系数。- 用第一批的结果消元得到第二批：
nums[3] = cnt['h'] - nums[8]，nums[5] = cnt['f'] - nums[4]，nums[7] = cnt['s'] - nums[6]。这三条式子成立的前提是右边被减去的数字已经确定，所以顺序不能提前。- 用前两批的结果解出最后两个：
nums[1] = cnt['o'] - nums[0] - nums[2] - nums[4]，nums[9] = cnt['i'] - nums[5] - nums[6] - nums[8]。注意nums[9]依赖第二批里的nums[5]，所以它必须排在 5 之后。- 从数字 0 到 9 依次遍历，把每个数字按它的个数追加到结果里。因为遍历顺序就是升序，所以天然满足输出要求，不需要再排序。
- 用可变字符缓冲区拼接结果并一次性转成字符串。输入规模到 $10^5$ 时，用不可变字符串反复拼接会退化成平方复杂度。
以
"fviefuro"走一遍：先统计字母，得到f出现 2 次，v、i、e、u、r、o各出现 1 次，其余为 0。第一批：nums[0] = cnt['z'] = 0，nums[2] = cnt['w'] = 0，nums[4] = cnt['u'] = 1，nums[6] = cnt['x'] = 0，nums[8] = cnt['g'] = 0。第二批：nums[3] = cnt['h'] - nums[8] = 0 - 0 = 0，nums[5] = cnt['f'] - nums[4] = 2 - 1 = 1，nums[7] = cnt['s'] - nums[6] = 0 - 0 = 0。第三批：nums[1] = cnt['o'] - nums[0] - nums[2] - nums[4] = 1 - 0 - 0 - 1 = 0，nums[9] = cnt['i'] - nums[5] - nums[6] - nums[8] = 1 - 1 - 0 - 0 = 0。最终只有nums[4] = 1和nums[5] = 1，从 0 到 9 遍历依次追加，得到"45"。
代码实现
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$ 为输入长度。统计字母是一次线性扫描，十个数字的消元是常数次运算，拼接结果的总字符数不超过 $n / 3$（最短的单词
six也有三个字母），因此整体保持线性。- 空间复杂度：$O(1)$，只用了长度 26 的字母计数数组和长度 10 的数字计数数组，都与输入规模无关；返回值本身属于必要输出，不计入额外空间。
关键点总结
- 一旦题目声明「顺序被打乱」，字符串就退化为字母的多重集，唯一可提取的信息是计数。这是所有变位词类问题的第一反应。
- 在一组互相耦合的等式里先找「只含一个未知数」的那条，解出来再回代，本质就是高斯消元的手工版。找唯一标识元素是把耦合系统解耦的通用手段。
- 求解顺序必须与依赖关系一致。把十个数字分成三批书写，能让依赖方向一目了然，也避免了「9 依赖 5」这种隐蔽的顺序陷阱。
- 输出要求升序，等价于只关心每个数字的出现次数，所以完全不需要（也无法）还原原始单词序列。识别出「不需要做的事」和识别出「需要做的事」同样重要。
- 面试视角：面试官想看的是你能否现场推出那张依赖关系，而不是背下五个魔法字母。可行的做法是把十个单词写在纸上，逐个字母数它出现在哪些单词里，当场圈出只出现一次的
z、w、u、x、g，推导过程本身就是最好的答案。- 面试视角：可以补一句「题目保证输入有效，所以省略了校验；若要写健壮版本，最后应检查所有字母计数都被恰好消耗为零，否则返回空串」，体现对前置条件的敏感度。
易错点总结
- 错误写法：
nums[9]漏掉eight的贡献，写成cnt['i'] - nums[5] - nums[6]。用例"eight"→cnt['i'] = 1，nums[5] = nums[6] = 0，算出nums[9] = 1，输出"89"，正确答案是"8"。- 错误写法：
nums[1]漏掉four的贡献，写成cnt['o'] - nums[0] - nums[2]。用例"four"→cnt['o'] = 1，算出nums[1] = 1，输出"14"，正确答案是"4"。- 错误写法：
nums[3]直接取cnt['h']，忘记扣掉eight。用例"eight"→cnt['h'] = 1，算出nums[3] = 1，输出"38"，正确答案是"8"。- 错误写法：把
nums[9]排在nums[5]之前计算。用例"five"→ 求nums[9]时nums[5]还是初始值 0，cnt['i'] = 1使nums[9] = 1，输出多出一个 9，正确答案是"5"。- 错误写法：以为
o是one的唯一标识，直接令nums[1] = cnt['o']。用例"zero"→cnt['o'] = 1被当成一个one，输出"01"，正确答案是"0"。- 错误写法：以为
n是nine的唯一标识。用例"one"→cnt['n'] = 1被判成一个nine，输出"19"之类结果；实际n还出现在one、seven里，而且nine自身带两个n，这条路径连系数都不对。- 错误写法：按数字被确定的先后顺序（0、2、4、6、8、3、5、7、1、9）拼接输出。用例
"owoztneoer"→ 得到nums[0] = nums[1] = nums[2] = 1，却输出成"021"，正确答案是升序的"012"。- 错误写法：用不可变字符串反复拼接（
ans += i）。用例 长度 $10^5$ 的输入 → 每次拼接都要复制整串，整体退化成 $O(n^2)$，直接超时。- 错误写法：Java 里把追加写成
builder.append((char) i)。用例"zero"→ 追加的是码点为 0 的控制字符而非字符'0'，输出是不可见的乱码；正确写法是追加整数i，或显式转成(char) ('0' + i)。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 242. 有效的字母异位词 | 简单 | 只需比较两串的字母计数是否完全相同，计数之间没有依赖需要消元 |
| 389. 找不同 | 简单 | 计数差值只剩一个字符，可以用求和或异或把空间压到常数 |
| 1002. 查找共用字符 | 简单 | 需要在多个字符串的计数之间逐位取最小值 |
| 451. 根据字符出现频率排序 | 中等 | 统计之后要按频次降序重排字符，考察计数与排序的衔接 |