＜leetcode＞17.电话号码的字母组合——DFS

＜leetcode＞17.电话号码的字母组合——DFS

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

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number

解答：

class Solution {
public:
    vector letterCombinations(string digits) {
        vector combinations;
        if(digits.empty()){
            return combinations;
        }
        map digmap = {
            {'2', "abc"},
            {'3', "def"},
            {'4', "ghi"},
            {'5', "jkl"},
            {'6', "mno"},
            {'7', "pqrs"},
            {'8', "tuv"},
            {'9', "wxyz"}
        };
        string combination;
        dfs(combinations, digits, digmap, 0, combination);
        return combinations;
    }

    void dfs(vector& combinations, const string& digits, const map& digmap, int index,string& combination){
        if(index == digits.size()){
            combinations.push_back(combination);//递归终止条件
        }else{
            char digit = digits[index];
            string letters = digmap.at(digit);
            for(const char& letter : letters){
                combination.push_back(letter);
                dfs(combinations, digits, digmap, index + 1, combination);
                combination.pop_back();
            }
        }
    }
};

深度优先搜索，类似于递归，关键在于回溯函数的写法，首先用map映射储存数字与字母之间的关系，然后将组合的字符串不断回溯。

注意：从字符串取出每个字符的类型为char，不能用string接收，会报类型错误；使用时加上引用可以避免拷贝造成的内存浪费，但引用类型的时候如果加上const，则该容器将不能修改。