LeetCode 17 电话号码的字母组合

17.电话号码的字母组合

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

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

DFS暴力法

此处的要求就是穷举，那么对于每一个数字中的每一个字母都需要选取一次，基本思想就是选取当前字母递归，在递归返回后，回溯选取（不选当前字母），进入到下一次递归中。

class Solution {
public:
    vector<string> letter={"abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    vector<string> res;
    string str;
    void DFS(string digits,int start){
        if(start==digits.size()){
            res.push_back(str);
            return;
        }
        string s=letter[digits[start]-'2'];
        for(int i=0;i<s.size();i++){
            str+=s[i];
            DFS(digits,start+1);
            str.pop_back();
        }
    }
    vector<string> letterCombinations(string digits) {
        if(digits.size()==0) return res;
        DFS(digits,0);
        return res;
    }
};