17. Letter Combinations of a Phone Number.md

17. 电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例:

输入："23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

说明:
尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。

解法一：

//时间复杂度O(3^n ?)), 空间复杂度O(n)
class Solution {
public:
    vector<string> letterCombinations(string digits) {
        if(digits.empty()) return {};
        unordered_map<char, string> um = { {'2', "abc"}, {'3', "def"}, {'4', "ghi"}, {'5', "jkl"}, 
                                           {'6', "mno"}, {'7', "pqrs"}, {'8', "tuv"}, {'9', "wxyz"} };
        vector<string> vec = {""};
        
        for(char digit : digits) {
            vector<string> temp;
            for(int i = 0; i < um[digit].size(); i++) {
                for(string str : vec) temp.push_back(str + um[digit][i]);
            }
            vec.swap(temp);
        }
        return vec;
    }
};

思路：

1. 构建一个映射um，表示数字与其对应的字符集合。
2. 初始vec只有一个元素（空串），然后遍历输入字符串digits；
3. 在遍历过程中每遇到一个字符，就将数组vec扩展为内容相同且长度为原vec3倍的重复数组（或4倍，看当前数字对应的字符个数），并且在依次每一个重复的段中当前数字对应的字符；
4. 遍历完成后，返回vec。

看字不直观，以输入"23"为例：

1. 初始时vec = {""}，开始遍历输入字符串"23"；
2. 遇到'2'，其对应字符为"abc"。所以我们就将vec扩展为3倍，此时vec = {"", "", ""}。然后在每一个重复段中依次加入'a'、'b'、'c'，此时vec = {"a", "b", "c"}；
3. 遇到'3'，其对应字符为"def"。所以我们就将vec扩展为3倍，此时vec = {"a", "b", "c", "a", "b", "c", "a", "b", "c"}。然后在每一个重复段中依次加入'd'、'e'、'f'，此时vec = {"ad", "bd", "cd", "ae", "be", "ce", "af", "bf", "cf"}。
4. 返回vec。

2019/09/19 21:37