难度: Medium
在老式手机上，用户通过数字键盘输入，手机将提供与这些数字相匹配的单词列表。每个数字映射到0至4个字母。给定一个数字序列，实现一个算法来返回匹配单词的列表。你会得到一张含有有效单词的列表。映射如下图所示：
示例 1:
输入: num = "8733", words = ["tree", "used"] 输出: ["tree", "used"]
示例 2:
输入: num = "2", words = ["a", "b", "c", "d"] 输出: ["a", "b", "c"]
提示：
num.length <= 1000words.length <= 500words[i].length == num.lengthnum中不会出现 0, 1 这两个数字运行时间: 32 ms
内存: 17.7 MB
string = ["abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]
DICT = {}
for i in range(2, 10):
for w in string[i-2]:
DICT[w] = str(i)
class Solution:
def getValidT9Words(self, num: str, words: List[str]) -> List[str]:
def check(va):
for j, x in enumerate(num):
if DICT[va[j]] != x:
return False
return True
return [word for word in words if check(word)]
本题解采用建立映射字典和遍历验证的方法。首先，建立一个映射字典DICT，将每个字母映射到对应的T9键盘数字上。然后，定义一个辅助函数check来验证给定单词的每个字母是否能通过映射字典DICT转换为输入的数字序列num。在主函数getValidT9Words中，通过列表推导式返回所有通过check验证的单词。
时间复杂度: O(n * m)
空间复杂度: O(1)
string = ['abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz'] # T9键盘的数字到字母的映射
DICT = {} # 字母到数字的映射字典
for i in range(2, 10):
for w in string[i-2]:
DICT[w] = str(i) # 建立字母到数字的映射
class Solution:
def getValidT9Words(self, num: str, words: List[str]) -> List[str]:
def check(va):
for j, x in enumerate(num):
if DICT[va[j]] != x: # 检查当前字母映射的数字是否与对应位置的数字匹配
return False
return True # 所有字母均匹配则返回True
return [word for word in words if check(word)] # 通过check验证的单词被添加到结果列表
通过使用预定义的字符串数组`string`，该数组已经按照T9键盘的布局将字母与数字对应起来。每个索引位置对应T9键盘上的一个数字，索引从0开始，对应数字2到9。循环通过这个数组，我将每个字母与其对应的数字（索引加2）关联起来，确保每个字母映射到正确的数字。这种方法简单且直接反映了T9键盘的字母到数字的映射关系。
使用循环来构建映射字典DICT可以减少错误和提高代码的可读性与维护性。直接定义一个完整的映射字典虽然在代码量上可能更少，但增加了手动输入错误的可能性，并且对于查看代码的人来说，理解映射关系的逻辑可能不如动态构建映射直观。循环构建映射确保每一次映射都是基于可验证的逻辑，从而减少错误。
使用enumerate函数可以同时获取索引和值，这在本题中非常有用，因为我们需要比较`num`中的每个数字是否与`va`（单词）中相应位置的字母通过字典DICT映射后的数字匹配。使用enumerate可以让我们在一个循环中完成这个任务，提高代码的清晰度和效率。另一种方法是使用常规for循环与索引访问，例如`for i in range(len(num)):`然后使用`num[i]`和`va[i]`进行比较，这与使用enumerate在功能上是等价的，但enumerate使代码更简洁。