題目介紹
題目：電話號(hào)碼的字母組合
描述：給定一個(gè)僅包含數(shù)字 2-9 的字符串宴倍，返回所有它能表示的字母組合服球。給出數(shù)字到字母的映射如下（與電話按鍵相同）俺亮。注意 1 不對(duì)應(yīng)任何字母估灿。
數(shù)字字母映射示例:
- 輸入："23"
輸出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].說明: 盡管上面的答案是按字典序排列的兢交，但是你可以任意選擇答案輸出的順序摩疑。
解析
如果還記得高中學(xué)過的排列組合問題匕累，就可以發(fā)現(xiàn)以上問題是一個(gè)最簡單的組合問題渡八。假設(shè)輸入了 n 個(gè)數(shù)字，每個(gè)數(shù)字所包含的字母個(gè)數(shù)分別是 m1, m2, ..., mn霞怀，那么解的個(gè)數(shù)則為：C1m1C1m2...C1mn 惫东，也就是m1*m2*...*mn。雖然這和我們的題目關(guān)系不大毙石，但是它限定了時(shí)間復(fù)雜度的下限廉沮，我們?cè)谠O(shè)計(jì)算法時(shí)可以參考此值。
首先徐矩，我們考慮最簡單的情況滞时，假如只輸入一個(gè)數(shù)字 2，那么答案的解集是{"a", "b", "c"}滤灯，現(xiàn)在坪稽，我們輸入第二個(gè)數(shù)字 3，那就是把 "d"鳞骤、"e"窒百、"f" 分別和 "a" 組合，然后和 "b" 組合豫尽，最后再與 "c" 組合篙梢。也就是說，我們得到前面的結(jié)果美旧，復(fù)制多份渤滞，每一個(gè)結(jié)果后都增加一個(gè)當(dāng)前的字符，就可以得到最終結(jié)果榴嗅，由此可以得出第一條思路：遞歸妄呕。參考代碼如下：
public List<String> letterCombinations(String digits) {
if(digits.length()==0)return new ArrayList<>();
String[] letters = {"abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
return letterCombinations(digits,letters,digits.length()-1);
}
private List<String> letterCombinations(String digits,String[] letters, int end) {
List<String> result = new ArrayList<>();
if (end==0) {
int index = digits.charAt(end)-'2';
for (int i = 0; i < letters[index].length(); i++) {
result.add(String.valueOf(letters[index].charAt(i)));
}
return result;
}else{
int index = digits.charAt(end)-'2';
for (int i = 0; i < letters[index].length(); i++) {
// 復(fù)制前一結(jié)果
List<String> temp = new ArrayList<>(letterCombinations(digits, letters, end-1));
for (int j = 0; j < temp.size(); j++) {
// 每一條結(jié)果后邊都加上當(dāng)前的一個(gè)字符
temp.set(j, temp.get(j)+letters[index].charAt(i));
}
result.addAll(temp);
}
}
return result;
}
但是以上的代碼并不完美，為了復(fù)制遞歸需要的數(shù)據(jù)嗽测，額外的執(zhí)行了一段for循環(huán)語句趴腋，大大增加了時(shí)間復(fù)雜度，而且由于無法使用StringBuilder等類來操作字符串的拼接论咏，額外創(chuàng)建了許多String變量优炬，又浪費(fèi)了大量的時(shí)間和空間。所以我們需要尋找一種能夠使用StringBuilder厅贪，又不需要多一層for循環(huán)的方法蠢护，這個(gè)方法就是：遞歸+回溯。
現(xiàn)在依然假設(shè)輸入了數(shù)字 2养涮，因?yàn)檫€要輸入更多的數(shù)字葵硕，所以這時(shí)還得不到最終結(jié)果，我們從數(shù)字 2 代表的結(jié)果中選擇一個(gè)字符存入到StringBuilder里贯吓，例如選擇了字符 'a'懈凹，現(xiàn)在StringBuilder里的結(jié)果就是 'a'。接下來輸入數(shù)字 3 之后悄谐，'d'介评、'e'、'f' 每個(gè)字符都要和 'a' 組合爬舰，那么我們可以把 'a' 固定在StringBuilder中们陆，加入 'd' 組成結(jié)果 "ad"，然后移除 'd' 再加入 'e'情屹，組成結(jié)果 'ae'坪仇，...。假如輸入了更多數(shù)字垃你，就依法炮制椅文，再固定 "ad"，然后加入 'g' 組成 "adg"惜颇，移除 'g' 再加入 'h' 組成 "adh"皆刺，...。這個(gè)過程就是回溯官还，之所以還有遞歸是因?yàn)槊看芜\(yùn)算只處理了一個(gè)輸入的數(shù)字芹橡。參考代碼如下：
public List<String> letterCombinations(String digits) {
List<String> result = new ArrayList<>();
if(digits.length()==0)return result;
String[] letters = {"abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
StringBuilder sb = new StringBuilder();
letterCombinations(digits, 0, letters, sb, result);
return result;
}
private void letterCombinations(String digits, int start,String[] letters, StringBuilder sb, List<String> result){
if(start==digits.length()){
if (sb.length()>0) {
result.add(sb.toString());
}
return;
}
if (digits.charAt(start)>='2'&&digits.charAt(start)<='9'){
for (int i = 0; i < letters[digits.charAt(start)-'2'].length(); i++) {
// 加入一個(gè)字符
sb.append(letters[digits.charAt(start)-'2'].charAt(i));
// 進(jìn)入下一級(jí)運(yùn)算
letterCombinations(digits, start+1, letters, sb, result);
// 刪除最后加入的字符
sb.deleteCharAt(sb.length()-1);
}
}else{
letterCombinations(digits, start+1, letters, sb, result);
}
}
可以看到遞歸+回溯算法的實(shí)現(xiàn)十分簡潔，但是也較為抽象望伦。接下來我們就以示例為例林说，看看輸入字符串為 "23" 時(shí)，代碼是如何執(zhí)行的屯伞。
首先腿箩，獲取到字符 '2' 時(shí)，函數(shù)進(jìn)到第一輪劣摇，代碼走到for循環(huán)中時(shí)把字符 'a' 添加到了 sb（StringBuilder實(shí)例）對(duì)象中珠移，然后就進(jìn)入了函數(shù)的第二輪，for循環(huán)將等待此遞歸函數(shù)執(zhí)行完成后再繼續(xù)運(yùn)行。這時(shí)獲取到字符 '3'钧惧，又把字符 'd' 添加到了sb中暇韧，進(jìn)入了下一輪的遞歸，也就是函數(shù)的第三輪浓瞪。
第三輪已經(jīng)得到了完整的結(jié)果懈玻，便return了，這時(shí)第二輪的函數(shù)繼續(xù)執(zhí)行乾颁，它把 sb 中的最后一個(gè)字符刪除涂乌，于是 sb 中又只剩下 'a'，for循環(huán)重復(fù)這個(gè)過程之后英岭，就得到了三個(gè)結(jié)果湾盒，分別是 "ad"，"ae"诅妹，"af"罚勾。
現(xiàn)在，第二輪的函數(shù)結(jié)束了漾唉，sb 中依然只剩下字符 'a'荧库，回到第一輪時(shí)繼續(xù)執(zhí)行刪除語句，便把 'a' 也刪除了赵刑，然后繼續(xù)處理 'b'分衫、處理 'c'，便得到了全部結(jié)果般此。
總結(jié)
其實(shí)早在研究KMP算法時(shí)蚪战，我們就見到過回溯的身影，之所以有KMP算法就是為了解決暴力算法的回溯問題铐懊，當(dāng)然不是任何情況下都能避免回溯的邀桑。
遞歸+回溯能夠解決很多實(shí)際的問題，之后的許多題目都可以用這個(gè)思路來解決科乎，但是這個(gè)算法較為抽象壁畸，需要我們多多練習(xí)，才能深刻理解茅茂。
相關(guān)源碼已經(jīng)上傳到我的Github捏萍。
下題預(yù)告
題目：四數(shù)之和
描述：給定一個(gè)包含 n 個(gè)整數(shù)的數(shù)組 nums 和一個(gè)目標(biāo)值 target，判斷 nums 中是否存在四個(gè)元素 a空闲，b令杈，c 和 d ，使得 a + b + c + d 的值與 target 相等碴倾？找出所有滿足條件且不重復(fù)的四元組逗噩。
注意：答案中不可以包含重復(fù)的四元組掉丽。
示例:
給定數(shù)組 nums = [1, 0, -1, 0, -2, 2]，和 target = 0异雁。
滿足要求的四元組集合為：[ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ]
我是飛機(jī)醬捶障，如果您喜歡我的文章，可以關(guān)注我~
編程之路片迅，道阻且長残邀。唯，路漫漫其修遠(yuǎn)兮柑蛇，吾將上下而求索。
