《程序员面试金典（第6版）》面试题 16.20. T9键盘（哈希映射，C++）

阿里云国内75折回扣微信号：monov8

阿里云国际，腾讯云国际，低至75折。AWS 93折免费开户实名账号代冲值优惠多多微信号：monov8 飞机：@monov6

题目描述

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

解题思路与代码

这道题呢是一道不算太难的题。因为其实很好有思路。

为什么呢看到这个键盘我脑子里就出现了俩字那就是“映射”对你猜的没错这道题其实就是去用哈希映射来解题。

哈希映射做的越好你这道题的复杂度其实也就越低。

那么接下来我们就看看如何用哈希映射来解决这个问题。

方法一使用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;
    }
};