题目重点：把词典单词编码成 2–9 数字串再比较，比暴力展开所有按键组合更适合大词典。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练版使用常见英文字母到数字 2–9 映射，字母大小写不敏感，只返回与整个数字串等长且完全相等的词，保留输入词典顺序与重复项。
- 0/1 没有字母、连字符与非 ASCII 字符返回无编码；输入数字若含 0/1 训练代码报错。原题是否允许空串、短语或词组合未知。
解题路线
- 单次查询把每个词逐字编码并与目标数字串比较；先按长度过滤，不能把前缀命中当完整匹配。若词典总字符数 T，扫描 O(T)。
- 若同一词典要回答 Q 个数字串，预处理每词编码并建数字串→原词列表，查询平均 O(1+输出量)；注意重复词是否保留由接口定义。
- 从数字串做 DFS 展开所有字母组合有最多 4^L 条路径，随后查词典；当词典规模有限、L 较长时远不如扫描或预建索引。Trie 可在 DFS 中剪掉无词前缀，但仍需按输入/查询量比较。
- 多词短语能否拼成目标数字串是另一道分词/回溯题，需要明确空格与词可重复规则，不能由这题目变体自动推断。
手动走一遍
数字 `8733` 与词典 tree、used、apple：tree 和 used 都编码为 8733，输出二者，apple 长度和编码均不符。训练代码经该例和 10,000 组随机词典/数字串对照。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
DIGITS = {
**dict.fromkeys("abc", "2"), **dict.fromkeys("def", "3"),
**dict.fromkeys("ghi", "4"), **dict.fromkeys("jkl", "5"),
**dict.fromkeys("mno", "6"), **dict.fromkeys("pqrs", "7"),
**dict.fromkeys("tuv", "8"), **dict.fromkeys("wxyz", "9"),
}
def encode_word(word: str) -> str | None:
try:
return "".join(DIGITS[ch] for ch in word.casefold())
except KeyError:
return None
def matching_words(words: list[str], digits: str) -> list[str]:
if any(ch not in "23456789" for ch in digits):
raise ValueError("digits must be 2..9")
return [word for word in words if encode_word(word) == digits]
复杂度
单次扫描 O(T)，O(L) 编码临时空间（L 最大词长）加输出；多查询索引预处理 O(T) 时间/空间，单次查询期望 O(1+R)，R 为结果词数。
易错点与追问
容易失分的边界
- 枚举 4^L 个字符组合而不利用给定词典。
- 只比较长度或前缀，漏完整相等。
- 把 0/1 随意映射字母。
- 多次查询每次重复编码整份词典。
- 把单词匹配扩成多个词拼接而未核证。
继续深挖
- 词典持续更新时索引怎么维护？
- 允许短语由多个词组成时如何做 DP/Trie？
- 大写、重音字母与标点怎么规范化？
- 重复词应去重还是保留输入顺序？
