給定一個僅包含數(shù)字 2-9 的字符串践叠，返回所有它能表示的字母組合恭垦。答案可以按 任意順序 返回。
給出數(shù)字到字母的映射如下（與電話按鍵相同）众雷。注意 1 不對應任何字母蒙兰。
示例.png
2對應abc 3對應def ... 9對應wxyz
分析:
其實就是給定一個數(shù)字組合的字符串，讓我們轉換成對應的所有字母組合排列；
有一個隱形條件就是雖然一個數(shù)字對應的是多個字母缝其，但一次只能拿出一個字母來配對，就像電話按鍵輸入一樣
思路：
考慮使用DFS(Depth-first search 深度優(yōu)先搜索)來解決此類問題徘六，很多排列組合相關的問題内边，都可以通過DFS來解決
class Solution {
private char[] cs;//字符數(shù)組
private List<String> list;//最終存放字符組合的數(shù)組
//記錄每一層選擇的字母，一趟結束后再轉成字符串就是一個字母組合咯
private char[] strings;
//數(shù)字字母對照表
private char[][] lettersArray = {
{'a','b','c'},{'d','e','f'},{'g','h','I'},
{'j','k','l'},{'m','n','o'},{'p','q','r','s'},
{'t','u','v'},{'w','x','y','z'}
};
public List<String> letterCombinations(String digits) {
//1.字符串為空 沒有意義
if(digits == null) return null;
//1.1 定義一個最終存放字符組合的數(shù)組
list = new ArrayList<>();
//1.2 轉字符數(shù)組
cs = digits.toCharArray();
//1.3 digits是空字符待锈，直接返回 list
if(cs.length==0) return list;
//1.4 字母組合數(shù)組的長度和cs等長即可
strings = new char[cs.length];
//2. 搜索字母組合
dfs(0);
//3. 返回字符組合的數(shù)組
return list;
}
//私有 沒有返回值 深度優(yōu)先搜索
//idx: 正在搜索第idx層
private void dfs(int idx) {
//1.已經(jīng)進入最后一層了 不能再深入 存起來得到的值
if(idx==cs.length) {
//得到一個正確的解漠其，就添加到數(shù)組中
list.add(new String(strings));
return;
}
//數(shù)字字符
char digit = cs[idx];
//數(shù)字字符減去'2'就是對應索引 (2~0 3~1 4~2 ...) 就得到 所有能選擇的字母
char[] letters = lettersArray[digit - '2'];
//2. 先枚舉這一層可以做的所有選擇
for(char letter : letters){
//取出其中一個字符記錄下來
strings[idx] = letter;
//下一層 自動回溯
dfs(idx + 1);
}
}
}
執(zhí)行結果.png
