17.電話號碼的字母組合

力扣題目鏈接//leetcode-cn.com/problems/letter-combinations-of-a-phone-number/

給定一個僅包含數(shù)字 2-9 的字符串，返回所有它能表示的字母組合。

給出數(shù)字到字母的映射如下（與電話按鍵相同）。注意 1 不對應(yīng)任何字母。

示例: 輸入："23" 輸出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

說明：盡管上面的答案是按字典序排列的，但是你可以任意選擇答案輸出的順序。

思路

從示例上來說，輸入"23"，最直接的想法就是兩層for循環(huán)遍歷了吧，正好把組合的情況都輸出了。

如果輸入"233"呢，那么就三層for循環(huán)，如果"2333"呢，就四層for循環(huán).......

大家應(yīng)該感覺出和77.組合遇到的一樣的問題，就是這for循環(huán)的層數(shù)如何寫出來，此時又是回溯法登場的時候了。

理解本題后，要解決如下三個問題：

1. 數(shù)字和字母如何映射
2. 兩個字母就兩個for循環(huán)，三個字符我就三個for循環(huán)，以此類推，然后發(fā)現(xiàn)代碼根本寫不出來
3. 輸入1 * #按鍵等等異常情況

數(shù)字和字母如何映射

可以使用map或者定義一個二位數(shù)組，例如：string letterMap[10]，來做映射，我這里定義一個二維數(shù)組，代碼如下：

conststringletterMap[10]={
"",//0
"",//1
"abc",//2
"def",//3
"ghi",//4
"jkl",//5
"mno",//6
"pqrs",//7
"tuv",//8
"wxyz",//9
};

回溯法來解決n個for循環(huán)的問題

對于回溯法還不了解的同學(xué)看這篇：關(guān)于回溯算法，你該了解這些！

例如：輸入："23"，抽象為樹形結(jié)構(gòu)，如圖所示：

圖中可以看出遍歷的深度，就是輸入"23"的長度，而葉子節(jié)點就是我們要收集的結(jié)果，輸出["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]。

回溯三部曲：

• 確定回溯函數(shù)參數(shù)

首先需要一個字符串s來收集葉子節(jié)點的結(jié)果，然后用一個字符串?dāng)?shù)組result保存起來，這兩個變量我依然定義為全局。

再來看參數(shù)，參數(shù)指定是有題目中給的string digits，然后還要有一個參數(shù)就是int型的index。

注意這個index可不是77.組合和216.組合總和III中的startIndex了。

這個index是記錄遍歷第幾個數(shù)字了，就是用來遍歷digits的（題目中給出數(shù)字字符串），同時index也表示樹的深度。

代碼如下：

vectorresult;
strings;
voidbacktracking(conststring&digits,intindex)

• 確定終止條件

例如輸入用例"23"，兩個數(shù)字，那么根節(jié)點往下遞歸兩層就可以了，葉子節(jié)點就是要收集的結(jié)果集。

那么終止條件就是如果index 等于 輸入的數(shù)字個數(shù)（digits.size）了（本來index就是用來遍歷digits的）。

然后收集結(jié)果，結(jié)束本層遞歸。

代碼如下：

if(index==digits.size()){
result.push_back(s);
return;
}

• 確定單層遍歷邏輯

首先要取index指向的數(shù)字，并找到對應(yīng)的字符集（手機鍵盤的字符集）。

然后for循環(huán)來處理這個字符集，代碼如下：

intdigit=digits[index]-'0';//將index指向的數(shù)字轉(zhuǎn)為int
stringletters=letterMap[digit];//取數(shù)字對應(yīng)的字符集
for(inti=0;i//處理
backtracking(digits,index+1);//遞歸，注意index+1，一下層要處理下一個數(shù)字了
s.pop_back();//回溯
}

注意這里for循環(huán)，可不像是在回溯算法：求組合問題！和回溯算法：求組合總和！中從startIndex開始遍歷的。

因為本題每一個數(shù)字代表的是不同集合，也就是求不同集合之間的組合，而77. 組合和216.組合總和III都是是求同一個集合中的組合！

注意：輸入1 * #按鍵等等異常情況

代碼中最好考慮這些異常情況，但題目的測試數(shù)據(jù)中應(yīng)該沒有異常情況的數(shù)據(jù)，所以我就沒有加了。

但是要知道會有這些異常，如果是現(xiàn)場面試中，一定要考慮到！

C++代碼

關(guān)鍵地方都講完了，按照關(guān)于回溯算法，你該了解這些！中的回溯法模板，不難寫出如下C++代碼：

//版本一
classSolution{
private:
conststringletterMap[10]={
"",//0
"",//1
"abc",//2
"def",//3
"ghi",//4
"jkl",//5
"mno",//6
"pqrs",//7
"tuv",//8
"wxyz",//9
};
public:
vector<string>result;
strings;
voidbacktracking(conststring&digits,intindex){
if(index==digits.size()){
result.push_back(s);
return;
}
intdigit=digits[index]-'0';//將index指向的數(shù)字轉(zhuǎn)為int
stringletters=letterMap[digit];//取數(shù)字對應(yīng)的字符集
for(inti=0;i//處理
backtracking(digits,index+1);//遞歸，注意index+1，一下層要處理下一個數(shù)字了
s.pop_back();//回溯
}
}
vector<string>letterCombinations(stringdigits){
s.clear();
result.clear();
if(digits.size()==0){
returnresult;
}
backtracking(digits,0);
returnresult;
}
};

一些寫法，是把回溯的過程放在遞歸函數(shù)里了，例如如下代碼，我可以寫成這樣：（注意注釋中不一樣的地方）

//版本二
classSolution{
private:
conststringletterMap[10]={
"",//0
"",//1
"abc",//2
"def",//3
"ghi",//4
"jkl",//5
"mno",//6
"pqrs",//7
"tuv",//8
"wxyz",//9
};
public:
vector<string>result;
voidgetCombinations(conststring&digits,intindex,conststring&s){//注意參數(shù)的不同
if(index==digits.size()){
result.push_back(s);
return;
}
intdigit=digits[index]-'0';
stringletters=letterMap[digit];
for(inti=0;i1,s+letters[i]);//注意這里的不同
}
}
vector<string>letterCombinations(stringdigits){
result.clear();
if(digits.size()==0){
returnresult;
}
getCombinations(digits,0,"");
returnresult;

}
};

我不建議把回溯藏在遞歸的參數(shù)里這種寫法，很不直觀，我在二叉樹：以為使用了遞歸，其實還隱藏著回溯這篇文章中也深度分析了，回溯隱藏在了哪里。

所以大家可以按照版本一來寫就可以了。

總結(jié)

本篇將題目的三個要點一一列出，并重點強調(diào)了和前面講解過的77. 組合和216.組合總和III的區(qū)別，本題是多個集合求組合，所以在回溯的搜索過程中，都有一些細節(jié)需要注意的。

其實本題不算難，但也處處是細節(jié)，大家還要自己親自動手寫一寫。

其他語言版本

Java

classSolution{

//設(shè)置全局列表存儲最后的結(jié)果
Listlist=newArrayList<>();

publicListletterCombinations(Stringdigits){
if(digits==null||digits.length()==0){
returnlist;
}
//初始對應(yīng)所有的數(shù)字，為了直接對應(yīng)2-9，新增了兩個無效的字符串""
String[]numString={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
//迭代處理
backTracking(digits,numString,0);
returnlist;

}

//每次迭代獲取一個字符串，所以會設(shè)計大量的字符串拼接，所以這里選擇更為高效的StringBuild
StringBuildertemp=newStringBuilder();

//比如digits如果為"23",num為0，則str表示2對應(yīng)的abc
publicvoidbackTracking(Stringdigits,String[]numString,intnum){
//遍歷全部一次記錄一次得到的字符串
if(num==digits.length()){
list.add(temp.toString());
return;
}
//str表示當(dāng)前num對應(yīng)的字符串
Stringstr=numString[digits.charAt(num)-'0'];
for(inti=0;i//c
backTracking(digits,numString,num+1);
//剔除末尾的繼續(xù)嘗試
temp.deleteCharAt(temp.length()-1);
}
}
}

Python

classSolution:
ans=[]
s=''
letterMap={
'2':'abc',
'3':'def',
'4':'ghi',
'5':'jkl',
'6':'mno',
'7':'pqrs',
'8':'tuv',
'9':'wxyz'
}

defletterCombinations(self,digits):
self.ans.clear()
ifdigits=='':
returnself.ans
self.backtracking(digits,0)
returnself.ans

defbacktracking(self,digits,index):
ifindex==len(digits):
self.ans.append(self.s)
return
else:
letters=self.letterMap[digits[index]]#取出數(shù)字對應(yīng)的字符集
forletterinletters:
self.s=self.s+letter#處理
self.backtracking(digits,index+1)
self.s=self.s[:-1]#回溯

python3：

classSolution:
defletterCombinations(self,digits:str)->List[str]:
res=[]
s=""
letterMap=["","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"]
ifnotlen(digits):returnres
defbacktrack(digits,index,s):
ifindex==len(digits):
returnres.append(s)
digit=int(digits[index])#將index指向的數(shù)字轉(zhuǎn)為int
letters=letterMap[digit]#取數(shù)字對應(yīng)的字符集
foriinrange(len(letters)):
s+=letters[i]
backtrack(digits,index+1,s)#遞歸，注意index+1，一下層要處理下一個數(shù)字
s=s[:-1]#回溯
backtrack(digits,0,s)
returnres