LeetCode 17. 电话号码的字母组合

题意

给出一个包含数字2-9的字符串，返回其能表示的字母组合。每个数字到字母的映射参照电话按键。

思路

• 想法1：直接把各种组合写出来，$O(3^{n} \times 4^m)$，其中$n$为对应3个字母的按键的个数，$m$为对应4个字母的按键的个数，且$n + m = len$。
• 想法2：原来只有上面的做法啊……

代码

class Solution {
public:
    vector<string> letterCombinations(string digits) {

        if(digits == "")    return {};

        string MP[11] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        int len = digits.size();
        vector<string> res = {""}, tem;

        for(int i = 0; i < len; ++i)
        {
            tem.clear();
            for(int j = 0; j < res.size(); ++j)
            {
//                cout << "j = " << j << endl;
                for(int k = 0; k < MP[digits[i] - '0'].size(); ++k)
                {
//                    cout << MP[digits[i] - '0'][k] << endl;
//                    cout << res[j] + MP[digits[i] - '0'][k] << endl;
                    tem.push_back(res[j] + MP[digits[i] - '0'][k]);
                }
            }
            res = tem;
        }
        return res;
    }
};

总结

大力出奇迹。