每日一道 LeetCode (54)：電話號(hào)碼的字母組合
?每天 3 分鐘，走上算法的逆襲之路。
?
前文合集
代碼倉(cāng)庫(kù)
GitHub：https://github.com/meteor1993/LeetCode
Gitee：https://gitee.com/inwsy/LeetCode
題目：電話號(hào)碼的字母組合
難度：「中等」
題目來(lái)源：https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/
給定一個(gè)僅包含數(shù)字 2-9 的字符串，返回所有它能表示的字母組合。
給出數(shù)字到字母的映射如下（與電話按鍵相同）。注意 1 不對(duì)應(yīng)任何字母。
示例:
輸入："23"
輸出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
說(shuō)明: 盡管上面的答案是按字典序排列的，但是你可以任意選擇答案輸出的順序。
解題思路
這道題看著有木有感覺(jué)很簡(jiǎn)單的樣子，至少我一開(kāi)始是覺(jué)得蠻簡(jiǎn)單的。
先使用哈希表定義一個(gè)字典：
static?final?Map?map?=?Map.of(
????'2',?"abc",?'3',?"def",?'4',?"ghi",?'5',?"jkl",
????'6',?"mno",?'7',?"pqrs",?'8',?"tuv",?'9',?"wxyz"
);
上面這個(gè)是在 JDK9 以后開(kāi)始支持的初始化方式，正好 LeetCode 也支持 JDK9 的語(yǔ)法，如果一定要用 JDK8 的話，emmmmmmmm：
Map?map?=?new?HashMap()?{{
????put('2',?"abc");
????put('3',?"def");
????put('4',?"ghi");
????put('5',?"jkl");
????put('6',?"mno");
????put('7',?"pqrs");
????put('8',?"tuv");
????put('9',?"wxyz");
}};
別問(wèn)我為啥要用 JDK9 的寫法，問(wèn)就是省紙。
接下來(lái)思考那個(gè)示例 「23」 ，首先程序先解析 2 ， 2 對(duì)應(yīng)了三個(gè)字母 abc ， 3 也對(duì)應(yīng)了三個(gè)字母 def ，這道題在最終輸出的結(jié)果集沒(méi)玩什么滑頭，直接就是所有的情況都排列出來(lái)就可以了，那么我可以套兩個(gè)循環(huán)，直接把所有的情況全都迭代出來(lái)。
但是題目上并沒(méi)有說(shuō)輸入的字符串一定是兩位的，如果是三位的那不就傻了。實(shí)際上是輸出的字符串有幾位就需要套幾層循環(huán)，好像不是很好寫啊。。。
這個(gè)時(shí)候，就需要用到一種不是很好理解，并且不是很好寫的方案了——遞歸。
使用遞歸的時(shí)候并不需要指定遞歸的次數(shù)，遞歸是直接遞歸到底的。
于是就有了下面這段代碼：
//?最終結(jié)果
private?List?res?=?new?ArrayList<>?();
//?組合形式
private?StringBuilder?sb?=?new?StringBuilder();
public?List?letterCombinations(String?digits)? {
????if?(digits.length()?==?0)?return?res;
????backtrack(digits,?0);
????return?res;
}
//?回溯函數(shù)
public?void?backtrack(String?digits,?int?index)?{
????if?(index?==?digits.length())?{
????????res.add(sb.toString());
????}?else?{
????????char?digit?=?digits.charAt(index);
????????String?letters?=?map.get(digit);
????????int?lettersCount?=?letters.length();
????????for?(int?i?=?0;?i?????????????sb.append(letters.charAt(i));
????????????backtrack(digits,?index?+?1);
????????????sb.deleteCharAt(sb.length()?-?1);
????????}
????}
}
整段代碼并不長(zhǎng)，而且看起來(lái)還很好理解，整體最核心的就是在那個(gè) for 循環(huán)里面的三句話：
sb.append(letters.charAt(i));
backtrack(digits,?index?+?1);
sb.deleteCharAt(sb.length()?-?1);
第一句話是先把當(dāng)前的值放入到我們的全局對(duì)象 sb 中，按照案例的 「23」 來(lái)演示的話就是先把 a 放到 sb 中，然后開(kāi)始遞歸進(jìn)下一次，這時(shí)候，我們第一個(gè)字符串全都是 a ，第二個(gè)字符串 3 對(duì)應(yīng)的可選值有 def ，接著我們把 d 也放到 sb 中，這時(shí) sb 中的值是 ad ，然后進(jìn)入下一次迭代，走到上面的那個(gè)判斷，把 sb 中的 ad 放入最終的輸出結(jié)果 res 中，然后遞歸往上走一層，刪除 sb 中的最后一個(gè)數(shù)，這時(shí) sb 中剩下的是 a ， for 循環(huán)進(jìn)入下一次循環(huán) ，像 sb 中添加一個(gè) e ，然后重復(fù)上面的過(guò)程。
上面這段解釋有點(diǎn)繞，可以多讀幾次，或者在代碼上多打幾個(gè)斷點(diǎn)手動(dòng) debug 一下，分分鐘就懂了。
