电话号码的字母组合
17. 电话号码的字母组合
题目：给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
电话号码对应图.png
输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
输入：digits = ""
输出：[]
输入：digits = "2"
输出：["a","b","c"]
自行解答：
解答1思路：
第一种办法解答和解答3有点类似，但是数据结构用的不太一样。
1:将数字对应的字符填充到map中
2：判断输入数字长度，长度为1，直接将字符填充到result中返回即可，大于1时，就相当于初始化2个vector中的result
3：每次将电话数字对应的char的值分别加上之前temresult中的每一个值 填充到result中去
4：填充完毕一次，先将上一轮积攒的temResult清空，再将result的值同步到temresult中，在进行下一个电话数字字符填充
5：返回result即可，具体代码如下：
vector<string> letterCombinations(string digits) {
vector<string> result;
if(digits.length() == 0){
return result;
}
//1：将电话号码数字填充到map中
map<char,string>allNum;
allNum.insert(pair<char,string>('2',"abc"));
allNum.insert(pair<char,string>('3',"def"));
allNum.insert(pair<char,string>('4',"ghi"));
allNum.insert(pair<char,string>('5',"jkl"));
allNum.insert(pair<char,string>('6',"mno"));
allNum.insert(pair<char,string>('7',"pqrs"));
allNum.insert(pair<char,string>('8',"tuv"));
allNum.insert(pair<char,string>('9',"wxyz"));
char num = NULL;
string numStr;
//2:判断长度，如果长度为1，直接将数字对应的char组成string，pusb_back到 //vector中即可返回,若长度大于1，则初始化result
if(digits.length()>=1){
num = digits[0];
numStr = (*allNum.find(num)).second;
for(int i = 0;i<numStr.length();i++){
string tem(1,numStr[i]);
result.push_back(tem);
}
}
if(digits.length()<2){
return result;
}
vector<string> temResult(result);
for(int i =1;i<digits.size();i++){
num = digits[i];
numStr = (*allNum.find(num)).second;
result.clear();
//3:每次将电话数字对应的char的值分别加上之前temresult中的每一个值填 //充到result中去
for(int j = 0;j<temResult.size();j++){
string temStr = temResult[j];
for(int m = 0;m<numStr.size();m++){
string temStrinner = temStr + numStr[m];
result.push_back(temStrinner);
}
}
//4:填充完毕一次，先将上一轮积攒的temResult清空，再将result的值同步到 //temresult中，在进行下一个电话数字字符填充
temResult.clear();
temResult = result;
}
return result;
}
解答2思路：
第二种解法也是官方解法，叫做回溯法，解答点说按题意要求一直找到一个满足题意的要求的解之后，向上返回，从另外的分支继续往下找，寻找下一个可能的值，直到找到所有的解，本质上也是一种暴力法，即穷举所有可能，本题解法有点类似深度优先遍历的意思。
1：将电话号码数字和对应的字符填充到map中
2：递归调用DFS函数，参数为
digits，输入的电话号码数字
index，当前要使用的电话数字在电话号码数字字符中的索引下标
allPhoneNum，电话号码数字和其代表的字符串
result，结果集，存放符合题意的所有字符串
oneResult，符合题意的任意一个解及其这个解的子集
因此函数调用的含义是：将digits字符中的第0个字符对用的所有可能结果填充到result中，每次的变量是index 和oneresult
3：在遍历第0个位置的时候，继续递归调用DFS，此时是将
将digits字符中的第1个字符对用的所有可能结果填充到result中，每次的变量是index 和oneresult，以此递归调用，递归函数退出的basecase 是如果某次index的值是digits 的长度，说明已经走到了最后，此时需要将其中的一个oneresult push_back到result中
4：找到一个符合条件的解之后，向上回溯，即将oneresult 的刚才截掉最后一个字符，在 尝试下一个可能的结
5：递归遍历完成之后所有符合的解全在result中，返回即可
class Solution_1 {
public:
vector<string> letterCombinations(string digits) {
vector<string> result;
if(digits.length() == 0){
return result;
}
//1：将电话号码数字和对应的字符填充到map中
map<char,string>allNum;
allNum.insert(pair<char,string>('2',"abc"));
allNum.insert(pair<char,string>('3',"def"));
allNum.insert(pair<char,string>('4',"ghi"));
allNum.insert(pair<char,string>('5',"jkl"));
allNum.insert(pair<char,string>('6',"mno"));
allNum.insert(pair<char,string>('7',"pqrs"));
allNum.insert(pair<char,string>('8',"tuv"));
allNum.insert(pair<char,string>('9',"wxyz"));
string oneresult = "";
//2：递归调用DFS函数
DFS(digits,0,allNum,result,oneresult);
//5：递归遍历完成之后所有符合的解全在result中
return result;
}
void DFS(const string &digits,int index,map<char,string> &allPhoneNum,vector<string> &result,string &oneResult ){
if(index ==digits.size()){
result.push_back(oneResult);
return;
}
char phoneNUm = digits[index];
string phoneNUmStr = (*allPhoneNum.find(phoneNUm)).second;
for(int i = 0;i<phoneNUmStr.size();i++){
oneResult +=phoneNUmStr[i];
//3:递归调用DFS函数，参数中index变成了index+1，onesult变成了
//oneResult +=phoneNUmStr[i]
DFS(digits,index+1,allPhoneNum,result,oneResult);
//4：找到一个符合条件的解之后，向上回溯，即将oneresult 的刚才截掉 //最后一个字符，在 尝试下一个可能的结
oneResult = oneResult.substr(0,oneResult.size()-1);
}
}
};
解答3思路：
解答3其实就是广度遍历，和解答1基本一样，只不过使用queue数据结构实现，更加优美和便于理解
1：将电话号码数字和字符填充到map中
2：调用BFS函数，参数的含义和上面思路2含义一致，只不过将vector换成了queue
3：判断index的值，index的值为digits.size()，即为递归调用的basecase，结束递归调用
4：判断index的值，若为0，直接将字符填充到queue中，继续递归调用自己，index变为index+1
5：若index不是0，且不需要退出，即将queue中的字符从队首拿出，并将队首的字符+index位置对应的字符组成新字符，进行 入队操作，循环此动作，循环的次数是进入此次递归函数时的queue的长度
6：步骤3和步骤4只会执行一个，2个不管哪个执行完成，均继续递归调用BFS，其中indenx变成了index+1，继续执行
7：递归结束之后将quque进行转移到vector中，即可返回
class Solution_2{
public:
vector<string> letterCombinations(string digits) {
vector<string> result;
if(digits.length() == 0){
return result;
}
//1：将电话号码数字和字符填充到map中
map<char,string>allNum;
allNum.insert(pair<char,string>('2',"abc"));
allNum.insert(pair<char,string>('3',"def"));
allNum.insert(pair<char,string>('4',"ghi"));
allNum.insert(pair<char,string>('5',"jkl"));
allNum.insert(pair<char,string>('6',"mno"));
allNum.insert(pair<char,string>('7',"pqrs"));
allNum.insert(pair<char,string>('8',"tuv"));
allNum.insert(pair<char,string>('9',"wxyz"));
queue<string> tem;
//2：调用BFS函数，参数的含义和上面思路2含义一致，只不过将vector换成了 //queue
BFS(0,digits,allNum,tem);
int temSize = tem.size();
//7：递归结束之后将quque进行转移到vector中
for(int i = 0;i<temSize;i++){
result.push_back(tem.front());
tem.pop();
}
cout<<"result2:"<<result.size()<<endl;
return result;
}
void BFS(int index,string digits, map<char,string> &phoneMap,queue<string> &temQueue){
//3：basecase，递归结束条件
if(index == digits.size()){
return;
}
if(index == 0){
//4：判断index的值，若为0，直接将字符填充到queue中，继续递归调用自 //己，index变为index+1
string firstStr = (*phoneMap.find(digits[index])).second;
for(int j = 0;j<firstStr.length();j++){
string oneChar(1,firstStr[j]);
temQueue.push(oneChar);
}
} else{
//5：若index不是0，且不需要退出，即将queue中的字符从队首拿出，并将 //队首的字符+index位置对应的字符组成新字符，进行 入队操作，循环此动 //作，循环的次数是进入此次递归函数时的queue的长度
string tem = temQueue.front() ;
int currentSize = temQueue.size();
string indexPhoneNum = (*phoneMap.find(digits[index])).second;
string temResult;
for(int i = 0; i <currentSize; i++){
tem =temQueue.front();
for(int k=0;k<indexPhoneNum.size();k++){
temResult = tem + indexPhoneNum[k];
temQueue.push(temResult);
}
temQueue.pop();
}
}
//6：步骤3和步骤4只会执行一个，2个不管哪个执行完成，均继续递归调用BFS， //其中indenx变成了index+1，继续执行
BFS(index+1,digits,phoneMap,temQueue);
}
}
