LeetCode 面试题 16.20. T9键盘

约 5 分钟
文章信息 7 个分类 3 个标签
分类
LeetCode CodeTop 中等 未解决 1-2 程序员面试金典（第 6 版） 微软
标签
数组 字符串 哈希表

题目描述

✅ 面试题 16.20. T9键盘

image-20260929105910942

题意分析

按 T9 键盘规则，每个小写字母对应数字 2 到 9 中的一个。给定数字串 num 和候选单词列表，返回编码恰好等于 num 的候选单词，而不是返回所有可能的字母组合。

解法：逐词验证 T9 映射

核心思路

[!blue]

虽然一个数字可以对应多个字母，但一个字母对应的数字是唯一的。既然候选单词已经给出，就逐个验证它们，不必从数字反向枚举组合。

先用固定键盘分组建立 charToDigit，下标 c - 'a' 保存字母 c 对应的数字字符。所有候选共用这张 26 项映射表；其中 7 对应 pqrs，9 对应 wxyz，这两组各有四个字母。

每个字母恰好产生一位数字，所以长度不同的单词不可能匹配。对等长候选逐位比较：任意一位不同就能确定整个编码不等，立即停止检查；若全部位置都相同，编码必然等于 num，将原单词加入答案。这同时给出了排除和接受候选的完整条件。

解题步骤

  1. 按数字 2 到 9 的键盘分组，构造字母到数字字符的查找表。
  2. 依次检查每个候选，长度不同则跳过。
  3. 为当前单词初始化匹配标记，逐位比较映射值与 num[i]；遇到不匹配就终止本词检查。
  4. 全部通过的单词加入答案，继续检查后续候选。按输入顺序追加，自然保留当前实现的结果顺序。

代码实现

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+WL)$，W 为候选数量，L 为数字串长度；题目中候选均与数字串等长，每个词最多检查 L 位。
  • 空间复杂度：除输出外为 $O(1)$。映射表固定为 26 项，其余只有循环和匹配状态。

关键点总结

[!green]

  • 字母到数字的确定映射，把匹配判断变成逐位比较。
  • 映射表在候选循环外建立一次，无需每个词重新构造。
  • 比较值必须都是数字字符，不能将整数数字与字符编码混用。

易错点总结

[!yellow]

  • 数字 7、9 各有四个字母，漏掉 s 或 z 会错误排除候选。
  • 表中若保存整数 2，再直接与字符 '2' 比较，两者编码并不相等。
  • 每个候选都要重新初始化匹配标记，前一个词失败不能影响下一个词。
  • Go 结果应从零长度开始追加，否则预置的空字符串也会出现在返回值中。

相似题目

题目 难度 关联与区别
17. 电话号码的字母组合 中等 原题从数字生成全部字母组合，本题已有词表，把每个单词正向映射成数字验证更直接。
49. 字母异位词分组 中等 若需要多次查询，可按单词的T9编码签名分组，复用规范键聚合同类词的思路。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2021/76120085
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！