Leetcode 热题 HOT 100 17.电话号码的字母组合（C++ 深搜+回溯）

Leetcode 热题 HOT 100 17.电话号码的字母组合（C++ 深搜+回溯）

---

题目

---

路漫漫其修远兮，刷题还得要用心！

一、题目解析

这是一道通过字母组合的问题，通过电话键上数字对应的字母经行组合输出，我们求解的方法是通过深度搜索+回溯的方法完成题目的求解！（提一句：不会搜索和回溯的小伙伴，要下来多多去学习哦，它们本质其实枚举，但在时间复杂度上有大的优化哦）

二、解题步骤

①：我们定义一个字符数组s2来储存，电话键上数字所对应的字母组；
②：我们定义动态字符数组s1来储存我们返回的最终值，定义s字符数组储存每次搜索的结果；
③：深搜函数（dfs)的参数定义，我们定义两个参数，第一个是引用题目给出的字符串digits，第二个是我们遍历的深度index（即输出时组合的字母个数）；
④：调用dfs()函数，返回字符串s1；
当然最主要的其实时dfs()函数的部分，所以我接下来会详细讲解这个部分：

1.dfs()如何完成深搜与回溯

①：结束的边界：
即：字符串digits的长度与index的深度相同时，即搜索一次了，将此时字符串s的结果存在s1中并结束本次搜索，代码块：

     if(index==digits.size())
        {
            s1.push_back(s);
            return ;
        }

②：dfs()的主要部分：
在dfs()中，我们首先定义一个整型ans=0,来记录digits中的第几个数字，再定义一个stirng s3来存取字符串s2中对应的电话键下的字母，最后便是遍历字符串数组s3，进行递归与回溯的 *** 作。代码如下：

 void dfs(const string& digits,int index)
    {
        if(index==digits.size())
        {
            s1.push_back(s);
            return ;
        }
        int ans=digits[index]-'0';//字符数字转数字
        string s3=s2[ans];//s3保存对应s2中的字符串
        for(int i=0;i<s3.size();i++)
        {
            s.push_back(s3[i]);//将s3中的字母存入s；
            dfs(digits,index+1);//进行下一步的递归，index+1;
            s.pop_back();//回溯
        }
    }

2.完整代码

代码如下：

class Solution {
private:
   const string s2[10]={" "," ","abc","dfe","ghi","jkl","mno","pqrs","tuv","wxyz"};
public:
    vector<string>s1;
    string s;
    void dfs(const string& digits,int index)
    {
        if(index==digits.size())
        {
            s1.push_back(s);
            return ;
        }
        int ans=digits[index]-'0';
        string s3=s2[ans];
        for(int i=0;i<s3.size();i++)
        {
            s.push_back(s3[i]);
            dfs(digits,index+1);
            s.pop_back();
        }
    }
    vector<string> letterCombinations(string digits) {
        s.clear();
        s1.clear();
        if(digits.size()==0)
        return s1;
       dfs(digits,0);
       return s1;
    }
};

---

总结

怎么说呢，我个人觉得这个题还是很好的，很有价值的，博主刚开始拿到这道题时，想的就是暴力，逐个枚举，但是做到一半发现明显不好实现，然后看了官方题解后，便转战到搜索、回溯方面想。如果还有小伙伴没有学习过搜索和回溯的话，理解起来可能有点困难，不过接下来去多多学习这个知识点就可以啦（搜索与回溯算法很重要哦！），若文章有不足之处，还望大佬指正哦！