LeetCode 面试题 16.20. T9键盘

2021-11-03 HGNULB 约 11 分钟

文章信息 7 个分类 · 3 个标签

分类

LeetCode CodeTop 中等 未解决 1-2 微软 程序员面试金典（第 6 版）

标签

数组 字符串 哈希表

目录 收起 展开

题目描述

✅ 面试题 16.20. T9键盘

题意分析

老式手机的 T9 键盘上，数字 2 到 9 各自对应一组字母（2 对应 abc，3 对应 def，……，7 对应 pqrs，9 对应 wxyz）。给定一串数字 num 和一个单词表 words，要求返回所有"按 T9 键盘输入后能得到 num"的单词，按它们在 words 中的原始顺序输出。

约束里最关键的信号是映射方向的不对称性：一个数字对应多个字母（一对多），但一个字母只对应唯一一个数字（多对一）。这意味着"把数字串还原成所有可能的单词"是指数级的（这正是 17. 电话号码的字母组合 干的事），而"把单词转成数字串"是确定性的、线性的。既然给了单词表，就应该走后者——正向验证而不是反向生成。

第二个信号是单词只由小写字母构成、数字只含 2-9，所以字母到数字的映射表可以用一个长度 26 的定长数组表示，不需要哈希表；查表是 $O(1)$ 的数组下标访问，常数比哈希更小。

边界上要覆盖：单词长度与 num 不等（可以直接跳过，省掉逐字符比较）；words 为空；没有任何单词匹配（返回空列表而不是 null）；以及输出顺序必须与 words 的原始顺序一致。

解法：逐词验证（预先构建映射）

核心思路

先看一个诱人但错误的方向：从 num 出发，枚举每一位数字对应的所有字母，生成所有可能的字符串，再去单词表里查。这条路的瓶颈是指数爆炸——每位数字有 3 到 4 个候选字母，长度为 L 的数字串会生成 $3^L$ 到 $4^L$ 个候选，L = 10 就已经是百万量级，而其中绝大多数根本不是合法单词，全是白算。

反过来想：映射的另一个方向是确定性的。字母 a 只可能由数字 2 打出，x 只可能由 9 打出——没有歧义。所以给定一个单词，把它逐字符翻译成数字串是 $O(L)$ 的一次线性变换，然后与 num 逐位比对即可。搜索空间从"所有字母组合"缩小到"给定的单词表"，规模从指数降到线性。

由此确定要预先准备的状态：一张 charToDigit 表，charToDigit[c - 'a'] 存放字母 c 对应的数字字符。不变量是：对任意小写字母 c，charToDigit[c - 'a'] 恒等于 T9 键盘上 c 所在的按键编号（以字符形式存储，便于直接与 num 中的字符比较）。这张表由固定的 9 组字母常量一次性构建，之后只读不写。

主流程则是：对 words 中的每个单词，先比长度（长度不同必然不匹配，$O(1)$ 剪掉），再逐字符比较 charToDigit[word[i] - 'a'] 与 num[i]，一旦不等立刻 break。全部相等就把这个单词加入答案。因为是按 words 的下标顺序遍历、命中即追加，输出顺序天然与输入一致，不需要额外排序。

值得注意的是把映射值存成字符 '0' + d 而不是整数 d：这样比较时可以直接和 num.charAt(i) 对比，省掉一次字符到数字的转换；否则每次比较都要写 num.charAt(i) - '0'，多一步运算也多一处出错机会。

解题步骤

• 先构建 charToDigit 映射表。用一个长度 10 的字符串数组 {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"} 描述键盘，下标即按键号；前两格留空是因为 1 和 0 不对应字母，留空能让下标与按键号直接对齐，避免做偏移换算。然后双重循环把每个字母写进 charToDigit，得到"字母 → 数字字符"的反向表。

• 表只建一次，放在循环外。若把建表写进逐词的循环里，每个单词都要重建一次 26 格的表，虽然复杂度量级不变（$O(26)$ 是常数），但白白多做 n 遍，是典型的"把不变量算在循环内"的坏味道。

• 遍历 words，第一步比长度。word.length() != num.length() 直接 continue。这是最便宜的剪枝：$O(1)$ 就排除掉一个候选，避免进入 $O(L)$ 的逐字符比较。

• 逐字符比较映射结果与 num 对应位。用 charToDigit[word.charAt(i) - 'a'] != num.charAt(i) 判断；一旦不等就置标志并 break，不要跑完整个单词——前缀已经不符，后面的字符没有任何检查价值。

• 全部字符匹配则把单词加入答案列表。按遍历顺序追加，输出顺序自动与 words 一致。

• 返回答案列表，无匹配时返回空列表（Java 是空的 ArrayList，Go 是 nil 切片，判题都接受）。

以 num = "8733"、words = ["tree", "used"] 走一遍：

建表阶段：d = 2 时把 a、b、c 都映射到 '2'；d = 3 时 d、e、f 映射到 '3'；…… d = 7 时 p、q、r、s 映射到 '7'；d = 8 时 t、u、v 映射到 '8'；d = 9 时 w、x、y、z 映射到 '9'。

处理 "tree"：长度 4 与 num 相同，继续。t → '8' 与 num[0] = '8' 相等；r → '7' 与 num[1] = '7' 相等；e → '3' 与 num[2] = '3' 相等；e → '3' 与 num[3] = '3' 相等。全部匹配，加入答案。

处理 "used"：长度 4，继续。u → '8' 与 '8' 相等；s → '7' 与 '7' 相等；e → '3' 与 '3' 相等；d → '3' 与 '3' 相等。也全部匹配，加入答案。

返回 ["tree", "used"]，正确——这个用例恰好展示了 T9 的一对多特性：两个不同的单词打出同一串数字。

再走一个长度剪枝和提前退出的例子：num = "2"、words = ["a", "b", "c", "ab", "d"]。"a" 长度 1，a → '2' 匹配，加入；"b"、"c" 同理加入；"ab" 长度 2 与 num 长度 1 不等，被长度检查直接 continue，一次字符比较都没做；"d" 长度 1，但 d → '3' 与 '2' 不等，第一个字符就 break，不再继续。最终返回 ["a", "b", "c"]，顺序与输入一致。

代码实现

class Solution {
    public List<String> getValidT9Words(String num, String[] words) {
        char[] charToDigit = buildCharToDigit();
        List<String> answer = new ArrayList<>();

        for (String word : words) {
            if (word.length() != num.length()) {
                continue;
            }

            boolean match = true;
            for (int i = 0; i < word.length(); i++) {
                if (charToDigit[word.charAt(i) - 'a'] != num.charAt(i)) {
                    match = false;
                    break;
                }
            }
            if (match) {
                answer.add(word);
            }
        }
        return answer;
    }

    private char[] buildCharToDigit() {
        String[] map = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        char[] charToDigit = new char[26];
        for (int d = 2; d <= 9; d++) {
            for (char c : map[d].toCharArray()) {
                charToDigit[c - 'a'] = (char) ('0' + d);
            }
        }
        return charToDigit;
    }
}

func getValidT9Words(num string, words []string) []string {
    charToDigit := buildCharToDigit()
    var answer []string

    for _, word := range words {
        if len(word) != len(num) {
            continue
        }

        match := true
        for i := 0; i < len(word); i++ {
            if charToDigit[word[i]-'a'] != num[i] {
                match = false
                break
            }
        }
        if match {
            answer = append(answer, word)
        }
    }
    return answer
}

func buildCharToDigit() []byte {
    t9 := []string{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}
    charToDigit := make([]byte, 26)
    for d := 2; d <= 9; d++ {
        for i := 0; i < len(t9[d]); i++ {
            c := t9[d][i]
            charToDigit[c-'a'] = byte('0' + d)
        }
    }
    return charToDigit
}

复杂度分析

• 时间复杂度：$O(26 + \sum_i

  words_i

  )$，实际上界是 $O(n \cdot L)$，n 为单词个数、L 为 num 的长度。建表是固定的 26 次写入；每个单词最多做 L 次字符比较，长度不符的单词只花 $O(1)$。相比"从数字生成所有字母组合"的 $O(4^L)$，这是数量级的差距。

• 空间复杂度：$O(1)$ 额外空间（不计输出）。charToDigit 固定 26 字节，键盘常量表固定 10 个短字符串，都与输入规模无关；答案列表最坏存下全部单词，属于输出本身而非额外开销。

关键点总结

• 映射是多对一时，永远选"验证"而不是"生成"。字母→数字唯一确定，数字→字母有歧义；沿着确定的方向走是线性的，沿着有歧义的方向走是指数的。看到"给了候选集 + 要筛选"的题，先判断哪个方向是函数（单值映射），就往哪个方向算。
• 值域小且连续时，用定长数组代替哈希表。26 个小写字母减去 'a' 就是下标，查表是一次数组访问，比哈希省掉计算散列和处理冲突的开销。哈希表要留给键无法紧凑编码的场景。
• 循环不变的预处理必须提到循环外。映射表与具体单词无关，建一次即可；把它写进内层循环虽然不改变复杂度量级，但会让常数翻几十倍，也是面试官一眼就能看出的实现瑕疵。
• 最便宜的剪枝放在最前面。长度比较是 $O(1)$、字符比较是 $O(L)$，所以先比长度；逐字符比较时一旦不符立刻 break，不要跑完整个单词。这个"按代价从低到高排列判断条件"的习惯适用于所有过滤类问题。
• 面试视角：主动对比 17. 电话号码的字母组合 说明两题的方向差异。面试官很可能顺势追问"如果不给单词表，要列出所有可能的单词呢"——那就是回溯生成，复杂度 $O(4^L \cdot L)$；而"如果单词表非常大且要多次查询同一个 num"，则应该反过来预处理：把每个单词的数字签名算好存进哈希表（键是数字串、值是单词列表），查询降到 $O(L)$。能把"验证 / 生成 / 预建索引"三种形态的适用条件说清楚，这题就答满了。

易错点总结

• 错误写法：从 num 出发回溯生成所有字母组合再去表里查 → 用例 num 长度为 10、words 只有 2 个单词：生成 $4^{10} \approx 10^6$ 个候选串，全部与两个单词比对，直接 TLE；而正向验证只需 20 次字符比较。
• 错误写法：省掉长度检查，直接逐字符比较 → 用例 num = "2"、words = ["abc"]：循环按 word.length() 走到 i = 1 时访问 num.charAt(1) 越界抛异常（Go 里是切片越界 panic）。长度检查不只是剪枝，还是越界防护。
• 错误写法：循环上界写成 num.length() 而不是 word.length()，同时又漏了长度检查 → 用例 num = "234"、words = ["ab"]：访问 word.charAt(2) 越界。两个串的下标必须先被长度检查绑定成相同范围。
• 错误写法：把 charToDigit 的值存成整数 d 却与 num.charAt(i) 直接比较 → 用例 num = "2"、words = ["a"]：2 与字符 '2'（ASCII 50）不相等，所有单词都被判不匹配，返回空列表。存字符或统一转成整数，两边必须同类型。
• 错误写法：键盘常量表写成 {"abc", "def", ...} 从下标 0 开始，却仍用 map[d] 访问 → 用例 num = "2"、words = ["a"]：map[2] 取到的是 "ghi"，a 被错误映射到 '2' 之外的数字，全表错位。要么前两格留空、要么访问时写 map[d - 2]，二选一但不能混。
• 错误写法：把 7 写成 "pqr"、9 写成 "wxy"（漏掉第四个字母） → 用例 num = "7"、words = ["s"]：s 的映射值是数组默认的 '\0'，与 '7' 不等，漏掉正确答案。T9 键盘上 7 和 9 各有 4 个字母，是最容易抄错的两行。
• 错误写法：charToDigit[c - 'a'] 写成 charToDigit[c] → 用例 words = ["a"]：下标 97 超出长度 26 的数组，越界抛异常。字符建索引必须减去基准 'a'。
• 错误写法：不匹配时用 continue 而不是 break 跳出内层循环 → 用例 num = "22"、words = ["ad"]：continue 只跳过当前字符继续比下一个，match 会被后面匹配的字符覆盖回 true（若写法是每轮重置标志），把不匹配的单词误加入答案。发现不符必须立刻终止内层循环。
• 错误写法：match 标志声明在外层循环之外且不重置 → 用例 words = ["d", "a"]、num = "2"：处理 "d" 时 match 被置为 false，处理 "a" 时没有重置，导致正确的 "a" 也被丢弃。每个候选的标志必须在自己那一轮开头初始化。
• 错误写法：把映射表的构建放进遍历 words 的循环体内 → 用例 words 有 $10^4$ 个单词：多做 $10^4$ 次建表，虽然仍是线性但常数放大几十倍；面试里会被直接指出"这段和单词无关，应该提到循环外"。
• 错误写法：Go 里 answer := make([]string, len(words)) 后用 append → 用例 words = ["a"]、num = "2"：切片一开始就有 1 个空字符串，append 追加在其后，返回 ["", "a"]，多出一个空串。要么写 make([]string, 0, len(words))，要么直接 var answer []string。
• 错误写法：为了"保证顺序"最后对答案排序 → 用例 words = ["tree", "abc"] 且两者都匹配：排序后变成字典序，与输入顺序不一致，判题失败。按下标遍历、命中即追加，顺序天然正确，任何额外排序都是画蛇添足。

相似题目

题目	难度	考察点
17. 电话号码的字母组合	中等	同一张键盘表但走"生成"方向，需要回溯枚举全部组合
205. 同构字符串	简单	映射未知需要边扫边建，且必须双向唯一，不像 T9 有固定映射表
290. 单词规律	简单	映射两端一边是字符一边是单词，同样要防止两个键映射到同一个值
49. 字母异位词分组	中等	同样把每个单词算出一个"签名"再归并，签名换成了排序后的字符串
面试题 16.02. 单词频率	中等	同为单词表上的查询题，重点在把代价前移到构造阶段