Medium
好久没写过recursion感觉什么backtracking这些都忘了怎么写了，这道题拿来回顾一下吧。画一画recursion tree. (画不下，b开头的答案没画）
image.png
helper函数的定义就是当前能组成的字符是sb, 当前所有储存的答案res,当前数字和char对应的map和给予的digits下，能组成哪些新的string，把这些string加到res里面。
注意几点：
- List要拿几个元素来initialize的话，要像这样写：
map.put(2, new ArrayList<>(Arrays.asList('a','b','c'))); - char to int的method：
Character.getNumericValue(char c);
class Solution {
public List<String> letterCombinations(String digits) {
List<String> res = new ArrayList<>();
if (digits == null || digits.equals("")){
return res;
}
Map<Integer, List<Character>> map = new HashMap<>();
map.put(2, new ArrayList<>(Arrays.asList('a','b','c')));
map.put(3, new ArrayList<>(Arrays.asList('d','e','f')));
map.put(4, new ArrayList<>(Arrays.asList('g','h','i')));
map.put(5, new ArrayList<>(Arrays.asList('j','k','l')));
map.put(6, new ArrayList<>(Arrays.asList('m','n','o')));
map.put(7, new ArrayList<>(Arrays.asList('p','q','r','s')));
map.put(8, new ArrayList<>(Arrays.asList('t','u','v')));
map.put(9, new ArrayList<>(Arrays.asList('w','x','y','z')));
StringBuilder sb = new StringBuilder();
helper(digits, sb, map, res);
return res;
}
private void helper(String digits, StringBuilder sb, Map<Integer, List<Character>> map, List<String> res){
if (sb.length() == digits.length()){
res.add(sb.toString());
return;
}
for (char c : map.get(Character.getNumericValue(digits.charAt(sb.length())))){
sb.append(c);
helper(digits,sb,map,res);
sb.deleteCharAt(sb.length() - 1);
}
}
}
