LeetCode第17题：电话号码的字母组合
这道题首先一看题目，号码数目不固定，那么肯定不能用循环，否则会嵌套很多层，这种题首先应该想到的是递归方案，能意识到应该用递归解法就很容易想出来了。
public static List<String> letterCombinations(String digits) {
if (digits.length() == 0) {
return new ArrayList<>();
}
Map<Character, List<String>> phoneMap = new HashMap<Character, List<String>>() {{
put('2', Arrays.asList("a", "b", "c"));
put('3', Arrays.asList("d", "e", "f"));
put('4', Arrays.asList("g", "h", "i"));
put('5', Arrays.asList("j", "k", "l"));
put('6', Arrays.asList("m", "n", "o"));
put('7', Arrays.asList("p", "q", "r", "s"));
put('8', Arrays.asList("t", "u", "v"));
put('9', Arrays.asList("w", "x", "y", "z"));
}};
return getStrings(phoneMap, digits);
}
/**
* 递归拼接，每次返回的都是当前第一位字符与剩下的结果乘出来的并集
* @param phoneMap
* @param digits
* @return
*/
public static List<String> getStrings(Map<Character, List<String>> phoneMap, String digits) {
if (digits.length() == 1) {
return new ArrayList<>(phoneMap.get(digits.charAt(0)));
}
List<String> first = phoneMap.get(digits.charAt(0));
List<String> subAns = letterCombinations(digits.substring(1, digits.length()));
List<String> ans = new ArrayList<>();
for (String subAn : subAns) {
for (String s : first) {
ans.add(s + subAn);
}
}
return ans;
}
