Medium

好久沒(méi)寫(xiě)過(guò)recursion感覺(jué)什么backtracking這些都忘了怎么寫(xiě)了，這道題拿來(lái)回顧一下吧。畫(huà)一畫(huà)recursion tree. (畫(huà)不下，b開(kāi)頭的答案沒(méi)畫(huà)）

image.png

helper函數(shù)的定義就是當(dāng)前能組成的字符是sb, 當(dāng)前所有儲(chǔ)存的答案res,當(dāng)前數(shù)字和char對(duì)應(yīng)的map和給予的digits下，能組成哪些新的string，把這些string加到res里面。

注意幾點(diǎn)：

• List要拿幾個(gè)元素來(lái)initialize的話，要像這樣寫(xiě)：
  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);
        }
    }
}