17. 电话号码的字母组合

题目

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

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

示例 1：

输入：digits = "23"

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

示例 2：

输入：digits = ""

输出：[]

示例 3：

输入：digits = "2"

输出：["a","b","c"]

提示：

• 0 <= digits.length <= 4
• digits[i] 是范围 ['2', '9'] 的一个数字。

解答（C++）

方法一

class Solution {
public:
    vector<string> ans;
    void dfs(string& current, string digits, int n) {
        if(current.length() == digits.length()) {
            ans.push_back(current);
            return ;
        }
        if(digits[n] == '2') {
            current += 'a';
            dfs(current, digits, n+1);
            current.pop_back();
            current += 'b';
            dfs(current, digits, n+1);
            current.pop_back();
            current += 'c';
            dfs(current, digits, n+1);
            current.pop_back();
        } else if (digits[n] == '3') {
            current += 'd';
            dfs(current, digits, n+1);
            current.pop_back();
            current += 'e';
            dfs(current, digits, n+1);
            current.pop_back();
            current += 'f';
            dfs(current, digits, n+1);
            current.pop_back();            
        } else if(digits[n] == '4') {
            current += 'g';
            dfs(current, digits, n+1);
            current.pop_back();
            current += 'h';
            dfs(current, digits, n+1);
            current.pop_back();
            current += 'i';
            dfs(current, digits, n+1);
            current.pop_back();             
        } else if(digits[n] == '5') {
            current += 'j';
            dfs(current, digits, n+1);
            current.pop_back();
            current += 'k';
            dfs(current, digits, n+1);
            current.pop_back();
            current += 'l';
            dfs(current, digits, n+1);
            current.pop_back();  
        } else if(digits[n] == '6') {
            current += 'm';
            dfs(current, digits, n+1);
            current.pop_back();
            current += 'n';
            dfs(current, digits, n+1);
            current.pop_back();
            current += 'o';
            dfs(current, digits, n+1);
            current.pop_back();  
        } else if(digits[n] == '7') {
            current += 'p';
            dfs(current, digits, n+1);
            current.pop_back();
            current += 'q';
            dfs(current, digits, n+1);
            current.pop_back();
            current += 'r';
            dfs(current, digits, n+1);
            current.pop_back();  
            current += 's';
            dfs(current, digits, n+1);
            current.pop_back(); 
        } else if(digits[n] == '8') {
            current += 't';
            dfs(current, digits, n+1);
            current.pop_back();
            current += 'u';
            dfs(current, digits, n+1);
            current.pop_back();
            current += 'v';
            dfs(current, digits, n+1);
            current.pop_back();  
        } else {
            current += 'w';
            dfs(current, digits, n+1);
            current.pop_back();
            current += 'x';
            dfs(current, digits, n+1);
            current.pop_back();
            current += 'y';
            dfs(current, digits, n+1);
            current.pop_back();  
            current += 'z';
            dfs(current, digits, n+1);
            current.pop_back();   
        }
    }
    vector<string> letterCombinations(string digits) {
        if(digits.size() == 0) return ans;
        string current;
        dfs(current, digits, 0);
        return ans;
    }
};

优化

class Solution {
public:
    vector<string> ans;
    void dfs(string& current, string digits, unordered_map<char, string> m, int n) {
        if(current.size() == digits.size()) {
            ans.push_back(current);
            return ;
        }
        string str = m[digits[n]];
        for(int i = 0; i < str.size(); ++i) {
            current.push_back(str[i]);
            dfs(current, digits, m, n+1);
            current.pop_back();
        }
    }
    vector<string> letterCombinations(string digits) {
        if(digits.length() == 0) return ans;
        unordered_map<char, string> m{
            {'2',"abc"},
            {'3',"def"},
            {'4',"ghi"},
            {'5',"jkl"},
            {'6',"mno"},
            {'7',"pqrs"},
            {'8',"tuv"},
            {'9',"wxyz"}
        };
        string current;
        dfs(current, digits, m, 0);
        return ans;
    }
};

解答（Python）