算法：深度优先遍历算法

本篇主要积累的是深度优先遍历算法

什么是深搜

深度优先搜索英文缩写为 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;}
};