题目描述
映射如下图所示：
示例 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 这两个数字
解题思路与代码
这道题呢，是一道不算太难的题。因为其实很好有思路。
为什么呢？看到这个键盘，我脑子里就出现了俩字，那就是“映射”，对，你猜的没错，这道题其实就是去用哈希映射来解题。
哈希映射做的越好，你这道题的复杂度其实也就越低。
那么接下来我们就看看如何用哈希映射来解决这个问题。
方法一： 使用unordered_map来解决这个问题。
- 其实真的很简单。我们创建一个
unordered_map<char,char> map，前面的key方的是26个因为字符，后面的value对应的是字符对应的数字。再创建一个结果集result。 - 之后用一个双层for循环去做遍历好了。外层for循环去遍历words里面的每一个单词，内层for循环去遍历每一个单词中的每一个字符。
- 我们用一个标记去判断内层的字符是否与num中的字符相对应。如果都对应，则添加到result之中。
- 最后返回result即可。
具体代码如下：
class Solution {
public:
vector<string> getValidT9Words(string num, vector<string>& words) {
vector<string> result;
unordered_map<char,char> map;
for(int i = 0; i < 15; ++i)
map['a' + i] = '0' + i / 3 + 2;
for(int i = 15; i < 19; ++i)
map['a' + i] = '0' + 7;
for(int i = 19; i < 22; ++i)
map['a' + i] = '0' + 8;
for(int i = 22; i < 27; ++i)
map['a' + i] = '0' + 9;
for(int i = 0; i < words.size(); ++i){
bool flag = true;
for(int j = 0; j < words[i].size(); ++j)
if(map[words[i][j]] != num[j]){
flag = false;
break;
}
if(flag) result.push_back(words[i]);
}
return result;
}
};
复杂度分析
时间复杂度：
- 在最坏的情况下，你需要检查所有的单词（长度为n的单词有m个）。对于每个单词，你需要检查所有的字母（最多n个），以确保它们都与给定的数字字符串匹配。因此，时间复杂度是O(mn)，其中m是单词列表的长度，n是单词和数字字符串的长度。
空间复杂度：
- 你使用了一个哈希表来存储字母到数字的映射，这个表的大小是固定的（26个英文字母），因此空间复杂度是O(1)。但是，如果考虑输出的空间，那么在最坏的情况下，你可能需要存储所有的单词，这将使空间复杂度变为O(m)。
方法二：优化！使用vector去做哈希映射
这种方法其实就是把26个字母对应的数字全部都遍历到一个vector里，然后其他步骤，和上一种做法无二差，但是节省了空间去存储字符，这种做法不需要去把字母作为key。
具体的代码如下：
class Solution {
public:
vector<string> getValidT9Words(string num, vector<string>& words) {
vector<string> result;
vector<char> map {'2','2','2','3','3','3','4','4','4','5','5','5','6','6','6','7','7','7','7','8','8','8','9','9','9','9'};
for(int i = 0; i < words.size(); ++i){
int flag = true;
for(int j = 0; j < words[i].size(); ++j)
if(map[words[i][j] - 'a'] != num[j]){
flag = false;
break;
}
if(flag) result.push_back(words[i]);
}
return result;
}
};
复杂度分析
时间复杂度：O(mn),其中m是单词的数量，n是单词的长度
空间复杂度：O(m),其中m是单词的数量。
总结
-
哈希映射：这道题目需要你设计一个哈希映射来实现字母到数字的转换。哈希映射是一种常见的数据结构，可以用来高效地查找和存储数据。
-
字符串处理：你需要处理输入的字符串，包括分析单词和数字序列，这要求你具有基本的字符串操作技巧。
-
逻辑思维和细节处理：你需要设计一个算法来判断单词是否与数字序列匹配，这需要你具有清晰的逻辑思维和对细节的把握。
此外，这道题目还具有实际的应用价值。例如，一些老式的手机键盘输入法就是使用类似的方法来实现的。每个数字键都对应几个字母，用户可以通过输入数字序列来输入单词。因此，理解和解决这个问题可以帮助你更好地理解这些实际应用背后的原理。
最后的最后，如果你觉得我的这篇文章写的不错的话，请给我一个赞与收藏，关注我，我会继续给大家带来更多更优质的干货内容。