电话号码的字母组合
给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。
给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。
![17.电话号码的字母组合](/i/ll/?i=2020102916424043.png)
示例:
- 输入:"23"
- 输出:["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
说明:尽管上面的答案是按字典序排列的,但是你可以任意选择答案输出的顺序
思路
题目给的例子好像可以用for循环解决,但是输入一旦变多,就又碍于for循环的深度限制而无法解决了
所以还是得用回溯
本题与 组合问题 很像,我们要解决的问题如下:
- 数字和字母之间如何映射?
- 用回溯解决for循环深度不足的问题,从而遍历出所有组合结果
数字和字母如何映射
可以使用map或者定义一个二维数组,例如:string letterMap[10],来做映射,这里定义一个二维数组,代码如下:
string letterMap[10] = {
"", //0
"", //1
"abc", //2
"def", //3
"ghi", //4
"jkl", //5
"mno", //6
"pqrs", //7
"tuv", //8
"wxyz" //9
};
代码分析
1、确定回溯函数的参数与返回值
首先需要一个字符串saveStr来收集叶子节点的结果,然后用一个字符串数组result保存起来,这两个变量依旧定义为全局变量
输入参数是题目给的digits,另外还需要一个参数index,用来指明当前遍历到了digits中的哪个数(index也表示树的深度)
class Solution {
//定义一个map用来映射数组与字母
private:
string letterMap[10] = {
...
};
//确定回溯函数的参数和返回值
vector<string> res;
string saveStr;//用于保存叶子结点出的字符串
void backtracking(string& digits, int index){//index是用来指明当前遍历到了digits中的哪个数
}
public:
vector<string> letterCombinations(string digits) {
}
};
2、确定终止条件
index等于输入数字个数就结束,相当于遍历完一遍digits
class Solution {
//定义一个map用来映射数组与字母
private:
string letterMap[10] = {
...
};
//确定回溯函数的参数和返回值
vector<string> res;
string saveStr;//用于保存叶子结点出的字符串
void backtracking(string& digits, int index){//index是用来指明当前遍历到了digits中的哪个数
//确定终止条件
if(index == digits.size()){//index等于输入数字个数就结束,即遍历完一遍digits
res.push_back(saveStr);
return;
}
}
public:
vector<string> letterCombinations(string digits) {
}
};
3、确定单层处理逻辑
首先要取index指向的数字,即从输入数字字符串取数字并转为整型
然后从映射表中取出对应数字的字母映射
class Solution {
//定义一个map用来映射数组与字母
private:
string letterMap[10] = {
"", //0
"", //1
"abc", //2
"def", //3
"ghi", //4
"jkl", //5
"mno", //6
"pqrs", //7
"tuv", //8
"wxyz" //9
};
//确定回溯函数的参数和返回值
vector<string> res;
string saveStr;//用于保存叶子结点出的字符串
void backtracking(string& digits, int index){//index是用来指明当前遍历到了digits中的哪个数
//确定终止条件
if(index == digits.size()){//index等于输入数字个数就结束,即遍历完一遍digits
res.push_back(saveStr);
return;
}
//确定单层处理逻辑
//从输入数字字符串取数字并转为整型
int singleDigi = digits[index] - '0';
//从映射表中取出对应数字的字母映射
string digiMap = letterMap[singleDigi];
for(int i = 0; i < digiMap.size(); ++i){
saveStr.push_back(digiMap[i]);
backtracking(digits, index + 1);
saveStr.pop_back();//回溯处理
}
}
public:
vector<string> letterCombinations(string digits) {
}
};
注意这里for循环是从0开始遍历,因为手机按键是从0~9
代码
class Solution {
//定义一个map用来映射数组与字母
private:
string letterMap[10] = {
"", //0
"", //1
"abc", //2
"def", //3
"ghi", //4
"jkl", //5
"mno", //6
"pqrs", //7
"tuv", //8
"wxyz" //9
};
//确定回溯函数的参数和返回值
vector<string> res;
string saveStr;//用于保存叶子结点出的字符串
void backtracking(string& digits, int index){//index是用来指明当前遍历到了digits中的哪个数
//确定终止条件
if(index == digits.size()){//index等于输入数字个数就结束,即遍历完一遍digits
res.push_back(saveStr);
return;
}
//确定单层处理逻辑
//从输入数字字符串取数字并转为整型
int singleDigi = digits[index] - '0';
//从映射表中取出对应数字的字母映射
string digiMap = letterMap[singleDigi];
for(int i = 0; i < digiMap.size(); ++i){
saveStr.push_back(digiMap[i]);
backtracking(digits, index + 1);
saveStr.pop_back();//回溯处理
}
}
public:
vector<string> letterCombinations(string digits) {
if(digits == "") return res;
backtracking(digits, 0);
return res;
}
};
注意点
1、数字字符串转为整型的操作
2、TBD
标签:digits,03,string,映射,index,saveStr,字母组合,LeetCode,数字 From: https://www.cnblogs.com/DAYceng/p/17196743.html