☎ 17.电话号码的字母组合
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
提示：
0 <= digits.length <= 4digits[i] 是范围 ['2', '9'] 的一个数字。
思路
基本思想
输入一串数字，对于每一个数字，都对应了不同的字符串，将每个数字对应的不同字符串组合起来，形成不同的组合
如果给定两个数字，那么就可以使用for循环嵌套，一层for循环遍历一个数字对应的字符串，但是一旦数字多了起来，那么for循环也就一层套一层，时间复杂度变得很高，所以考虑使用回溯法解决当前的问题
对于每一个数字来说，其对应的字符串都可以看做是回溯算法中的一层，这样只需要控制当前遍历到哪一个数字，取出当前数字对应的字符串，然后继续下一层遍历，取出下一个数字对应的字符串，每一层都遍历一个数字对应的字符串
所以整体代码的逻辑就是控制start来遍历给定的digits中的每一个数字，对于每一个数字，取出背后对应的字符串来形成不同的组合
将每个数字对应的字符串当成回溯法中的一层
执行流程
- 判断当前是否遍历到了digits的最后一个元素，是的话说明形成了一个新的组合，此时记录当前的组合并且返回
- 根据记录的下标找到当前需要遍历的数字
- 根据当前需要遍历的数字找到当前需要遍历的字符串
- 将字符串的元素依次加入组合中
- 进行下一层的遍历
start记录的是当前遍历到了digits中的第几个数字
代码
根据以上分析，得出以下代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
| class Solution {
public:
//需要先建立映射关系，然后遍历digits中的每一个元素，将他们对应的string进行组合
//回溯法的一层就是digits中的一个元素
//每一层都遍历digits中的一个元素对应的若干字符
vector<string> res;
string path="";
string letter[10]={
"",
"",
"abc",
"def",
"ghi",
"jkl",
"mno",
"pqrs",
"tuv",
"wxyz"
};
vector<string> letterCombinations(string digits) {
if(digits.size()==0)
return res;
backtrack(0,digits);
return res;
}
//start代表遍历到了digits的哪一个元素
void backtrack(int start,string digits){
//一旦遍历到了digits的末尾，说明形成了一个字母组合
if(start==digits.size()){
res.push_back(path);
return;
}
//找到当前需要遍历的数字
int num=digits[start]-'0';
//根据数字找到对应的字符串
string charac=letter[num];
//遍历对应的字符串
for(auto c:charac){
//新形成一个字符串
path.push_back(c);
//遍历digits中的下一个数字对应的字符串
backtrack(start+1,digits);
path.pop_back();
}
}
};
|
总结
需要转换思维，将每个数字对应的字符串当成回溯法中的一层，start记录的是当前遍历到了digits中的第几个元素，其余的与回溯法没有什么区别
