程序员面试金典 - 面试题 16.20. T9键盘

题目难度: 中等

原题链接

今天继续更新程序员面试金典系列, 大家在公众号 算法精选 里回复 面试金典 就能看到该系列当前连载的所有文章了, 记得关注哦~

题目描述

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

解决方案

思路

• 我们首先可以建立每个数字到映射字母的字典
• 然后遍历每个单词, 对于其每个字母, 检查它是否可以从对应下标的数字映射得到
• 如果某个单词的全部字母都可以通过对应数字映射得到, 则说明该单词与数字相匹配, 将其加入最终结果
• 下面的代码对必要步骤有详细的解释, 方便大家理解

复杂度

• 时间复杂度 O(NC): N 是单词个数, C 是单词长度, 需要两重循环, 所以时间复杂度是O(NC)
• 空间复杂度 O(1): 只使用了常数空间的变量

代码

class Solution:
    def getValidT9Words(self, num: str, words: List[str]) -> List[str]:
        # maps字典存储每个数字映射后的字母
        maps = {
            "2": "abc",
            "3": "def",
            "4": "ghi",
            "5": "jkl",
            "6": "mno",
            "7": "pqrs",
            "8": "tuv",
            "9": "wxyz",
        }
        res = []
        for w in words:
            # 遍历每个单词, 检查其是否可以由num映射得到
            for i, c in enumerate(w):
                if c not in maps[num[i]]:
                    # 这个单词的当前字符c不可能由num的第i位得到, 说明这个单词不匹配, 直接break
                    break
            else:
                # 没有break, 则说明这个单词匹配, 将其加入最终结果
                res.append(w)
        return res

大家可以在下面这些地方找到我~😊

我的 GitHub

我的 Leetcode

我的 CSDN

我的知乎专栏

我的头条号

我的牛客网博客

我的公众号: 算法精选, 欢迎大家扫码关注~😊