本篇主要积累的是深度优先遍历算法
什么是深搜
深度优先搜索英文缩写为 DFS 即Depth First Search
其过程是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次
简单来说就是: 一路走到头，不撞墙不回头
典型题目积累
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
这里可以把它想象成是一个多叉树，每次都是多叉树的前序遍历，深度优先进行遍历，当遍历到根部的时候再转换另外一个根进行遍历，假设以258为例：
思路：从输出结果看，输出的是vector<string>，因此第一步要首先把每一个内容组装起来，比如要先组装成ajt,aju等，再把这些字符串尾插到vector中，因此思路就很明显了
class Solution { const char* numarray[10]={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"}; public: void Combine(string& digits,int i,string CombineStr,vector<string>& v) { if(i==digits.size()) { v.push_back(CombineStr); return; } int num=digits[i]-'0'; string str=numarray[num]; for(auto ch : str) { Combine(digits,i+1,CombineStr+ch,v); } } vector<string> letterCombinations(string digits) { vector<string> v; if(digits.size()==0) { return v; } string str; Combine(digits,0,str,v); return v; } };
递归展开图如下所示：
