济南建站方案,体育新闻最新消息世界杯,官网建设费,软件工程就业方向和前景文章目录 什么是深搜典型题目积累 本篇主要积累的是深度优先遍历算法
什么是深搜
深度优先搜索英文缩写为 DFS 即Depth First Search
其过程是对每一个可能的分支路径深入到不能再深入为止#xff0c;而且每个节点只能访问一次
简单来说就是: 一路走到头#xff0c;不撞墙… 文章目录 什么是深搜典型题目积累 本篇主要积累的是深度优先遍历算法
什么是深搜
深度优先搜索英文缩写为 DFS 即Depth First Search
其过程是对每一个可能的分支路径深入到不能再深入为止而且每个节点只能访问一次
简单来说就是: 一路走到头不撞墙不回头
典型题目积累
电话号码和字母组合
给定一个仅包含数字 2-9 的字符串返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下与电话按键相同。注意 1 不对应任何字母。 这里可以把它想象成是一个多叉树每次都是多叉树的前序遍历深度优先进行遍历当遍历到根部的时候再转换另外一个根进行遍历假设以258为例 思路从输出结果看输出的是vectorstring因此第一步要首先把每一个内容组装起来比如要先组装成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,vectorstring v){if(idigits.size()){v.push_back(CombineStr);return;}int numdigits[i]-0;string strnumarray[num];for(auto ch : str){Combine(digits,i1,CombineStrch,v);}}vectorstring letterCombinations(string digits) {vectorstring v;if(digits.size()0){return v;}string str;Combine(digits,0,str,v);return v;}
};递归展开图如下所示
