力扣第十七题（电话号码的字母组合）详解

该题目的描述简单易懂，生活中是很常见，解题的方法和思路是用哈希表储存相应的值和字符串，下面给出的思路中中心思想大致相同。

方法一：回溯法。具体思路，先用数组储存相应的字符串，然后从输入的字符串中从索引0开始，将对应得到的字符串加入到字符串s中，然后索引加一，继续得到下一个字符对应的字符串，如果索引的值等于字符串的长度，则将其加入到result中，并进行回退，继续进行下一个。

class Solution {
private:
    const string letterMap[10] = {
        "", // 0
        "*", // 1
        "abc", // 2
        "def", // 3
        "ghi", // 4
        "jkl", // 5
        "mno", // 6
        "pqrs", // 7
        "tuv", // 8
        "wxyz", // 9
    };
public:
    vector<string> result;
    string s;
    void backtracking(const string& digits, int index) {
        if (index == digits.size()) {
            result.push_back(s);
            return;
        }
        int digit = digits[index] - 0;        // 将index指向的数字转为int
        string letters = letterMap[digit];      // 取数字对应的字符集
        for (int i = 0; i < letters.size(); i++) {
            s.push_back(letters[i]);            // 处理
            backtracking(digits, index + 1);    // 递归，注意index+1，一下层要处理下一个数字了
            s.pop_back();                       // 回溯
        }
    }
    vector<string> letterCombinations(string digits) {
        s.clear();
        result.clear();
        if (digits.size() == 0) {
            return result;
        }
        backtracking(digits, 0);
        return result;
    }
};

方法二：具体的思路是建立一个哈希表储存数字和对应字符串的。其余思路与上一个相同。

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        unordered_map<char, string> table{
            {0, " "}, {1,"*"}, {2, "abc"},
            {3,"def"}, {4,"ghi"}, {5,"jkl"},
            {6,"mno"}, {7,"pqrs"},{8,"tuv"},
            {9,"wxyz"}};  
        vector<string> res;
        if(digits == "") return res;
        func(res, "", digits, table, 0);
        return res;
    }
    
    void func(vector<string> &res, string str, string &digits, unordered_map<char, string> &m, int k){
        if(str.size() == digits.size()){
            res.push_back(str);
            return;
        }
        string tmp = m[digits[k]];
        for(char w : tmp){
            str += w;
            func(res, str, digits, m, k+1);
            str.pop_back();
        }
        return ;
    }
};