LeetCode 面试题 16.20. T9键盘

Categories:

题目描述
思路分析
1. 解法一：哈希表预处理（推荐）
2. 解法二：逐词遍历验证
相似题目

题目描述

✅ 面试题 16.20. T9键盘

思路分析

解法一：哈希表预处理（推荐）

核心思路：

建立 T9 键盘映射：每个数字对应若干字母（2→abc，3→def，…，9→wxyz）

对每个单词，将其字母序列转化为对应的数字串，以数字串为 key 分组存储到哈希表

查询时直接返回 num 对应的单词列表；若不存在返回空列表

复杂度分析：

时间复杂度：O(L)，其中 L 表示所有单词的字母总数，预处理一次后查询 O(1)

空间复杂度：O(L)，哈希表存储所有映射关系

class Solution {
    // T9 键盘数字到字母的映射
    private static final String[] T9_MAP = {
        "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"
    };

    public List<String> getValidT9Words(String num, String[] words) {
        // 构建字母到数字的反向映射
        char[] charToDigit = new char[26];
        for (int digit = 2; digit <= 9; digit++) {
            for (char c : T9_MAP[digit].toCharArray()) {
                charToDigit[c - 'a'] = (char) ('0' + digit);
            }
        }

        // 对每个单词生成对应数字串，分组存入哈希表
        Map<String, List<String>> map = new HashMap<>();
        for (String word : words) {
            StringBuilder sb = new StringBuilder();
            for (char c : word.toCharArray()) {
                sb.append(charToDigit[c - 'a']);
            }
            String key = sb.toString();
            map.computeIfAbsent(key, k -> new ArrayList<>()).add(word);
        }

        // 返回 num 对应的单词列表
        return map.getOrDefault(num, new ArrayList<>());
    }
}

func getValidT9Words(num string, words []string) []string {
    // T9 键盘数字到字母的映射
    t9Map := []string{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}

    // 构建字母到数字的反向映射
    charToDigit := make([]byte, 26)
    for digit := 2; digit <= 9; digit++ {
        for _, c := range t9Map[digit] {
            charToDigit[c-'a'] = byte('0' + digit)
        }
    }

    // 对每个单词生成对应数字串，分组存入哈希表
    groupMap := make(map[string][]string)
    for _, word := range words {
        key := make([]byte, len(word))
        for i, c := range word {
            key[i] = charToDigit[c-'a']
        }
        k := string(key)
        groupMap[k] = append(groupMap[k], word)
    }

    // 返回 num 对应的单词列表
    if result, ok := groupMap[num]; ok {
        return result
    }

    return []string{}
}

解法二：逐词遍历验证

核心思路：

不预处理，直接对每个单词逐字符与 num 对应位置比较

若单词长度与 num 长度相同，且每个字母对应的数字与 num 对应位置一致，则加入结果

复杂度分析：

时间复杂度：O(W × L)，其中 W 表示单词数量，L 表示单词平均长度

空间复杂度：O(1)，不计返回值

class Solution {
    // T9 键盘字母到数字的映射表
    private static final char[] CHAR_TO_DIGIT = new char[26];

    static {
        String[] t9Map = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        for (int d = 2; d <= 9; d++) {
            for (char c : t9Map[d].toCharArray()) {
                CHAR_TO_DIGIT[c - 'a'] = (char) ('0' + d);
            }
        }
    }

    public List<String> getValidT9Words(String num, String[] words) {
        List<String> result = new ArrayList<>();

        for (String word : words) {
            // 长度不匹配直接跳过
            if (word.length() != num.length()) {
                continue;
            }

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

            if (match) {
                result.add(word);
            }
        }

        return result;
    }
}

func getValidT9Words(num string, words []string) []string {
    // 构建字母到数字的映射
    t9Map := []string{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}
    charToDigit := make([]byte, 26)
    for d := 2; d <= 9; d++ {
        for _, c := range t9Map[d] {
            charToDigit[c-'a'] = byte('0' + d)
        }
    }

    var result []string

    for _, word := range words {
        // 长度不匹配直接跳过
        if len(word) != len(num) {
            continue
        }

        match := true
        for i, c := range word {
            if charToDigit[c-'a'] != num[i] {
                match = false
                break
            }
        }

        if match {
            result = append(result, word)
        }
    }

    return result
}

相似题目

题目	难度	考察点
49. 字母异位词分组	中等	哈希表、字符串
242. 有效的字母异位词	简单	哈希表、字符串
290. 单词规律	简单	哈希表、字符串
205. 同构字符串	简单	哈希表、字符串
336. 回文对	困难	哈希表、字符串
916. 单词子集	中等	哈希表、字符串

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2021/76120085