17. 电话号码的字母组合

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

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

示例:

输入：“23”

输出：[“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”].

说明:

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

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        if(digits.empty()) return {};
        vector<vector<char>> d(10);

        d[0] = {' '};
        d[1] = {};
        d[2] = {'a', 'b', 'c'};
        d[3] = {'d', 'e', 'f'};
        d[4] = {'g', 'h', 'i'};
        d[5] = {'j', 'k', 'l'};
        d[6] = {'m', 'n', 'o'};
        d[7] = {'p', 'q', 'r', 's'};
        d[8] = {'t', 'u', 'v'};
        d[9] = {'w', 'x', 'y', 'z'};

        vector<string> ans{""};
        for(char digit : digits)
        {
            vector<string> tmp;
            for(const string& s : ans)
            {
                for(char c : d[digit - '0'])
                {
                    tmp.push_back(s+c);
                }
            }
            ans.swap(tmp);
        }
        return ans;
    }
};

时间复杂度：O(4^n)

空间复杂度：O(〖2×4〗^n)

DFS：

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        if(digits.empty()) return {};
        vector<vector<char>> d(10);
        d[0] = {' '};
        d[1] = {};
        d[2] = {'a', 'b', 'c'};
        d[3] = {'d', 'e', 'f'};
        d[4] = {'g', 'h', 'i'};
        d[5] = {'j', 'k', 'l'};
        d[6] = {'m', 'n', 'o'};
        d[7] = {'p', 'q', 'r', 's'};
        d[8] = {'t', 'u', 'v'};
        d[9] = {'w', 'x', 'y', 'z'};
        //cur存储中间结果
        string cur;
        //ans存储最终答案
        vector<string> ans;
        dfs(digits, d, 0, cur, ans);
        return ans;
    }
private:
    //dfs遍历所有答案
    void dfs(const string& digits, const vector<vector<char>>& d, int l, string& cur, vector<string>& ans)
    {
        //递归的结束条件
        if( l == digits.length())
        {
            //当前递归结束时，将结果存入ans，并返回
            ans.push_back(cur);
            return;
        }
        //for循环遍历当前数字中的字母
        for(const char c: d[digits[l] - '0'])
        {
            cur.push_back(c);
            dfs(digits,d,l+1,cur,ans);
            //一次深度优先搜索完成时，删除cur中元素以便进行回溯
            cur.pop_back();
        }
    }
};

时间复杂度：O(4^n) n为输入的长度

空间复杂度：O(4^n+n)

[[C++]Leetcode超高效刷题顺序及题目详解笔记（持续更新中）]