原文链接: https://leetcode-cn.com/problems/t9-lcci

英文原文

On old cell phones, users typed on a numeric keypad and the phone would provide a list of words that matched these numbers. Each digit mapped to a set of 0 - 4 letters. Implement an algo­rithm to return a list of matching words, given a sequence of digits. You are provided a list of valid words. The mapping is shown in the diagram below:

Example 1:

Input: num = "8733", words = ["tree", "used"]
Output: ["tree", "used"]

Example 2:

Input: num = "2", words = ["a", "b", "c", "d"]
Output: ["a", "b", "c"]

Note:

• num.length <= 1000
• words.length <= 500
• words[i].length == num.length
• There are no number 0 and 1 in num.

中文题目

在老式手机上，用户通过数字键盘输入，手机将提供与这些数字相匹配的单词列表。每个数字映射到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 这两个数字

通过代码

高赞题解

解题思路

列表生成器形式的剪枝，缩小搜索空间

代码

class Solution:
    def getValidT9Words(self, num: str, words: List[str]) -> List[str]:
        kb = {'2':'abc', '3':'def', '4':'ghi', '5':'jkl', '6':'mno', '7':'pqrs', '8':'tuv', '9':'wxyz'}
        ns = list(num)
        candidate = words
        for i, n in enumerate(ns):
            candidate = [w for w in candidate if w[i] in kb[n]]

        return candidate

统计信息

通过次数	提交次数	AC比率
9399	12990	72.4%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言