计算机低能儿从0刷leetcode | 17.电话号码的数字组合 | 回溯思想

题目：17. 电话号码的字母组合

解答：看题解学习到这种思想叫做回溯法，学习了一下，这是建立在DFS的基础上搜索思路，还分为递归式回溯以及非递归式回溯，这道题使用的是递归回溯。递归回溯的大致框架如下：

void DFS(int i){//搜索第i层
    if(i>n){//搜索结束
               //结果处理(输出结果,方案计数等)
    }

    for(int j=下界;j<=上界;j++){
        if(限界函数&&约束条件){//满足限界函数和约束条件
            x[i]=j;//保存当前层的结果
            ...//回溯入场准备工作
            DFS(i+1);//搜索下一层
            ...//回溯退回清理工作
        }
    }
}

原文链接：https://blog.csdn.net/u011956367/article/details/120555480

应用在本题中，那就是：

class Solution {
public:
    string temp;//暂存字符串
    vector <string> res;//存储结果
    vector<string>map={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    

    void Back(int index, string digits){
        if(index==digits.size()) {//终止条件
            res.push_back(temp);
            return;
        }
   
        int num = digits[index]-'0';//根据数字字符的ASCII码，定位到上面map中对应的字符串下标
        string letter = map[num];//取出对应的元素，如“abc”
        for(int i=0;i<letter.size();i++){
            temp.push_back(letter[i]);
            Back(index+1,digits);
            temp.pop_back();
        }
    }



    vector<string> letterCombinations(string digits) {
        if(digits.empty()==true) return res;
         Back(0, digits);
         return res;
    }
};