題目地址

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

題目描述

在老式手機(jī)上，用戶通過數(shù)字鍵盤輸入，手機(jī)將提供與這些數(shù)字相匹配的單詞列表。每個(gè)數(shù)字映射到0至4個(gè)字母。給定一個(gè)數(shù)字序列，實(shí)現(xiàn)一個(gè)算法來返回匹配單詞的列表。你會(huì)得到一張含有有效單詞的列表。映射如下圖所示：

示例 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中不會(huì)出現(xiàn) 0, 1 這兩個(gè)數(shù)字

思路

1. 字典法，我們把每個(gè)數(shù)字可能的字符存下來，遍歷words數(shù)組，再看每個(gè)word的字符是否匹配輸入的數(shù)字。
   PS：和前綴樹有點(diǎn)類似，num的第i個(gè)數(shù)字就是前綴樹的第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);
    }

    /**
     * 執(zhí)行用時(shí)：5 ms, 在所有 Java 提交中擊敗了80.99%的用戶
     * 內(nèi)存消耗：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;
    }
}