LeetCode 题解

积跬步，至千里。

T9键盘

分类：程序员面试金典题解 标签： 数组 发布于：2020-05-20 ID：16.2

题目描述

来源于 https://leetcode-cn.com/

在老式手机上，用户通过数字键盘输入，手机将提供与这些数字相匹配的单词列表。每个数字映射到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 {
public:
    vector<string> getValidT9Words(string num, vector<string>& words) {
        vector<string> keys{"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        unordered_map<char, int> char_to_num;
        for(int i=0;i<keys.size();i++){
            for(char ch: keys[i]){
                char_to_num[ch] = i + '2';
            }
        }

        vector<string> ret;
        for(string& word: words){
            if(match(num, word, char_to_num)){
                ret.push_back(word);
            }
        }

        return ret;
    }

    bool match(const string& num, const string& word, unordered_map<char, int>& char_to_num){
        if(word.size() != num.size()){
            return false;
        }
        for(int i=0;i<num.size();i++){
            if(num[i] != char_to_num[word[i]]){
                return false;
            }
        }
        return true;
    }
};