Medium
好久沒寫過recursion感覺什么backtracking這些都忘了怎么寫了，這道題拿來回顧一下吧制市。畫一畫recursion tree. (畫不下残拐，b開頭的答案沒畫）
image.png
helper函數(shù)的定義就是當(dāng)前能組成的字符是sb, 當(dāng)前所有儲存的答案res,當(dāng)前數(shù)字和char對應(yīng)的map和給予的digits下刹孔，能組成哪些新的string，把這些string加到res里面标沪。
注意幾點(diǎn)：
- 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);
}
}
}
