这题是递归比迭代清晰多了。这个dfs挺有意思的，我一直在想怎么用for循环递归不同的值，没想出来，看了答案豁然开朗。从前脑子里没有for+递归那种一层层向下的模型，现在再看这种题，脑子里自然就有了那种N皇后一样的n*n的矩阵模型。
private static final String[] KEYS = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
public List<String> letterCombinations(String digits) {
List<String> res = new ArrayList<>();
dfs(res, digits, 0, "");
return res;
}
private void dfs(List<String> res, String digits, int index, String item) {
if (index == digits.length()) {
res.add(item);
return;
}
String s = KEYS[digits.charAt(index) - '0'];
for (int i = 0; i < s.length(); i++) {
dfs(res, digits, index + 1, item + s.charAt(i));
}
}
输入"234"，
一层层打印出来是这样的:
0 = "adg"
1 = "adh"
2 = "adi"
3 = "aeg"
4 = "aeh"
5 = "aei"
6 = "afg"
7 = "afh"
8 = "afi"
9 = "bdg"
10 = "bdh"
11 = "bdi"
12 = "beg"
13 = "beh"
14 = "bei"
15 = "bfg"
16 = "bfh"
17 = "bfi"
18 = "cdg"
19 = "cdh"
20 = "cdi"
21 = "ceg"
22 = "ceh"
23 = "cei"
24 = "cfg"
25 = "cfh"
26 = "cfi"
https://discuss.leetcode.com/topic/6380/my-recursive-solution-using-java
