#yyds干货盘点# LeetCode程序员面试金典：T9键盘

题目：

在老式手机上，用户通过数字键盘输入，手机将提供与这些数字相匹配的单词列表。每个数字映射到0至4个字母。给定一个数字序列，实现一个算法来返回匹配单词的列表。你会得到一张含有有效单词的列表。映射如下图所示：

示例 1:

输入: num = "8733", words = ["tree", "used"]

输出: ["tree", "used"]

示例 2:

输入: num = "2", words = ["a", "b", "c", "d"]

输出: ["a", "b", "c"]

代码实现：

class Solution {

    public List<String> getValidT9Words(String num, String[] words) {
        // 根据提供的words字典，构建字典树
        Trie trie = new Trie();
        for (String word : words) {
            trie.insert(word);
        }
        // 根据号码num和word字典，查找字典树
        List<String> res = new ArrayList<>();
        for (String word : words) {
            if (trie.search(word, num)) {
                res.add(word);
            }
        }
        return res;
    }
}

class TrieNode {
    TrieNode[] son = new TrieNode[26];
    boolean isEnd;
    char val; // 关键：val代表 "该字母" 对应的 "按键号码"，例如 "a、b、c" 对应号码 "1"
}

class Trie {
    TrieNode root;
    Map<Character, Character> map = new HashMap<>(); // 存放 “字母” 与 “按键号” 的对应关系

    public Trie() {
        root = new TrieNode();
        map.put('!', '1');
        map.put('@', '1');
        map.put('#', '1');
        map.put('a', '2');
        map.put('b', '2');
        map.put('c', '2');
        map.put('d', '3');
        map.put('e', '3');
        map.put('f', '3');
        map.put('g', '4');
        map.put('h', '4');
        map.put('i', '4');
        map.put('j', '5');
        map.put('k', '5');
        map.put('l', '5');
        map.put('m', '6');
        map.put('n', '6');
        map.put('o', '6');
        map.put('p', '7');
        map.put('q', '7');
        map.put('r', '7');
        map.put('s', '7');
        map.put('t', '8');
        map.put('u', '8');
        map.put('v', '8');
        map.put('w', '9');
        map.put('x', '9');
        map.put('y', '9');
        map.put('z', '9');
        map.put('+', '*');
        map.put('_', '0');
        map.put('↑', '#');
    }
    
    public void insert(String word) {
        TrieNode cur = root;
        for (char c : word.toCharArray()) {
            int cNum = c - 'a';
            if (cur.son[cNum] == null) {
                cur.son[cNum] = new TrieNode();
            }
            cur.son[cNum].val = map.get(c); // 每个节点的val存储 字母 对应的 按键号，例如 a、b、c 对应 1
            cur = cur.son[cNum];
        }
        cur.isEnd = true;
    }

    public boolean search(String word, String num) {
        TrieNode cur = root;
        int numIndex = 0;
        for (char c : word.toCharArray()) {
            int cNum = c - 'a';
            if (cur.son[cNum] == null || cur.son[cNum].val != num.charAt(numIndex)) {
                return false;
            } 
            numIndex++;
            cur = cur.son[cNum];
        }
        return cur.isEnd;
    }
}