17. 电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回全部它能表示的字母组合。git

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

解题思路： 看到组合排列之类的题，基本上想到的是用深度优先遍历中回溯算法解题，这个应该造成条件反射，而后视题目对算法时间的要求再考虑是否须要作剪枝操做。回溯算法的特征是，维护一条可伸缩的路径，好比我代码中使用的string out，而后在递归深刻的时候push元素，在递归退出即回溯的时候，pop元素，回溯算法基本是按照这种方式解题的，而后剪枝操做发生在递归动做以前，当发现不必递归时（好比显然再递归下去也找不到合理的解，或者说此时递归下去的状况在以前的递归中已经作过）那么咱们能够直接break掉。OK，这题只要按照回溯的思想解题，基本就没问题了，即，先处理第pos位置的各类状况，而后在递归的处理pos+1位置的各类状况，请看下面代码。算法

class Solution {
public:
    void helper(string digits, int pos, string out, vector<string>& res) {
        if (pos == digits.size()) {
            res.push_back(out);
            return;
        }
        for (int j = 0; j < mp[digits[pos] - '0'].size(); ++j) {
            out.push_back(mp[digits[pos] - '0'][j]);
            helper(digits, pos + 1, out, res);
            out.pop_back();
        }
    }
    vector<string> letterCombinations(string digits) {
        if (digits.empty()) return {};
        vector<string> res;
        helper(digits, 0, {}, res);
        return res;
    }
private:
    vector<string> mp = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
};