网站建设的国内外现状,制作英文,百度电脑版官网入口,wordpress怎么实现注册功能在我们的座机上#xff0c;都有这种数字与字母对应的按键。 以此为例#xff0c;讲解多叉树的深度优先遍历 问题
给定一个仅包含数字 2-9 的字符串#xff0c;返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下#xff08;与电话按键相同…在我们的座机上都有这种数字与字母对应的按键。 以此为例讲解多叉树的深度优先遍历 问题
给定一个仅包含数字 2-9 的字符串返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下与电话按键相同。注意 1 不对应任何字母。
示例 1
输入digits 23
输出[ad,ae,af,bd,be,bf,cd,ce,cf]示例 2
输入digits
输出[]示例 3
输入digits 2
输出[a,b,c] 0 digits.length 4digits[i] 是范围 [2, 9] 的一个数字。 分析
假设我们输入的是 2 5 8 那么对应元素分别是abc jkl tuv。一共有3*3*3 27钟组合。我们的思路是
先从2中取a再从5中取j再从8中取t。将三个字母存放到一个字符串中。再将不断组合好的字符串push_back到vectorstring中
完成好一组之后到达最深再返回再组合a j u再push_back。 代码
class Solution {
private:const char* numStrArr[10] {,,abc,def,ghi,jkl,mno,pqrs,tuv,wxyz}; //存放字符串的数组public:void Combine(const string digits, int i, string combineStr,vectorstring ret){if (i digits.size()) //深度遍历{ret.push_back(combineStr);return;}int num digits[i] - 0;string str numStrArr[num]; //数字映射的字母for (auto ch : str) //取一个字符去排列组合{Combine(digits,i1,combineStrch,ret);}}vectorstring letterCombinations(string digits) {vectorstring v; //存放字符串组合string str; if (digits.empty())return v;Combine(digits,0, str,v);return v;}
};
几个对象的功能digits,0, str,v
digits存储输入的字符串
0作为下标不断遍历字符串知道到达size()为止
str将映射好的数据存储到str中
v:返回数组 核心代码
string str numStrArr[num]; //数字映射的字母 for (auto ch : str) //取一个字符去排列组合 { Combine(digits,i1,combineStrch,ret); } 假设还是 2 5 8 。取到2的首字母之后进入递归取5的首字母。继续递归取到8的首字母。
再push_back
回到循环继续取8的第二个字母 等到5的首字母取完之后再取5的第二个字母继续递归。 剖解代码
通过上述的分析我们可以得出
1.需要靠一个递归完成遍历。递归的返回条件是深度达到size
2.既然是数字与字母的映射那就需要借助下标去不断遍历读取到的字符串
3.在不断加深的过程中应该靠的是 而不是这样return之后就可以回到原来的字符串 经验总结
当我们直接上手可能不会那么容易。但是显然的是这是存放在容器中的数据。因此理所应到要去考虑到用什么类型的数据结构去存放数据。从而想到该用什么方式去遍历。
对于树最好的方法就是递归遍历想好返回条件。
其次
1.最终要的是递归要分析好return条件
2.当需要深度遍历时一般需要借助下标 i
3.用到的是 而不是
