2021-02-28 面试题 16.20. T9键盘

题目地址

https://leetcode-cn.com/problems/t9-lcci/

题目描述

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

示例 1:
输入: num = "8733", words = ["tree", "used"]
输出: ["tree", "used"]
示例 2:
输入: num = "2", words = ["a", "b", "c", "d"]
输出: ["a", "b", "c"]

提示：
num.length <= 1000
words.length <= 500
words[i].length == num.length
num中不会出现 0, 1 这两个数字

思路

1. 字典法，我们把每个数字可能的字符存下来，遍历words数组，再看每个word的字符是否匹配输入的数字。
   PS：和前缀树有点类似，num的第i个数字就是前缀树的第i层。

题解

/**
 * @Author: vividzcs
 * @Date: 2021/2/28 11:20 上午
 */
public class GetValidT9Words {
    public static void main(String[] args) {
        GetValidT9Words instance = new GetValidT9Words();
        String num = "8733";
        String[] words = {"tree", "used"};
        List<String> result = instance.getValidT9Words(num, words);
        System.out.println(result);
    }

    /**
     * 执行用时：5 ms, 在所有 Java 提交中击败了80.99%的用户
     * 内存消耗：40.4 MB, 在所有 Java 提交中击败了38.80%的用户
     */
    public List<String> getValidT9Words(String num, String[] words) {
        Map<Character, Set<Character>> dict = getMap();
        List<String> result = new ArrayList<>();
        for (int i=0; i<words.length; i++) {
            String word = words[i];
            if (!matchWord(dict, word, num)) {
                continue;
            }
            result.add(word);
        }

        return result;
    }

    private boolean matchWord(Map<Character, Set<Character>> dict, String word, String num) {
        for (int j=0; j<word.length(); j++) {
            Character c = word.charAt(j);
            if (!dict.get(num.charAt(j)).contains(c)) {
                return false;
            }
        }
        return true;
    }
    private Map<Character, Set<Character>> getMap() {
        Map<Character, Set<Character>> dict = new HashMap<>();
        dict.put('2', new HashSet<>(Arrays.asList('a','b','c')));
        dict.put('3', new HashSet<>(Arrays.asList('d','e','f')));
        dict.put('4', new HashSet<>(Arrays.asList('g','h','i')));
        dict.put('5', new HashSet<>(Arrays.asList('j','k','l')));
        dict.put('6', new HashSet<>(Arrays.asList('m','n','o')));
        dict.put('7', new HashSet<>(Arrays.asList('p','q','r', 's')));
        dict.put('8', new HashSet<>(Arrays.asList('t','u','v')));
        dict.put('9', new HashSet<>(Arrays.asList('w','x','y','z')));
        return dict;
    }
}