LeetCode17. *的字母组合

☆☆☆思路：递归。本题是典型的树形问题　　

　　　　　使用StringBuilder要比拼接String效率高，但注意需要回溯操作。

class Solution {
    List<String> res; // 作为类的一个成员变量
    String[] map = new String[]{
            "",
            "",
            "abc",
            "def",
            "ghi",
            "jkl",
            "mno",
            "pqrs",
            "tuv",
            "wxyz"
    };
    public List<String> letterCombinations(String digits) {
        res = new ArrayList<>();
        if (digits == null || digits.length() == 0) return res;
//        dfs(digits, 0, "");
        dfs1(digits, 0, new StringBuilder()); // 使用StringBuilder，需要回溯操作
        return res;
    }
    // s中保存了此时从digits[0...index-1]翻译得到的一个字母字符串
    // 寻找和digits[index]匹配的字母，获得digits[0...index]翻译得到的解
    private void dfs(String digits, int index, String s) {
        if (index == digits.length()) {
            res.add(s);
            return;
        }
        char digit = digits.charAt(index);
        String letters = map[digit - '0'];
        for (int i = 0; i < letters.length(); i++) {
            dfs(digits, index + 1, s + letters.charAt(i));
        }
    }

    /**
     *  因为StringBuilder传入的都是同一个对象，所以在递归完成之后必须撤回上一次的操作，
     *  需要删除上一次添加的字符。
     *  而String每次改变之后传入的都是不同的对象。故无需撤销操作。
     */
    private void dfs1(String digits, int index, StringBuilder sb) {
        if (index == digits.length()) {
            res.add(sb.toString());
            return;
        }
        char digit = digits.charAt(index);
        String letters = map[digit - '0'];
        for (int i = 0; i < letters.length(); i++) {
            sb.append(letters.charAt(i));
            dfs1(digits, index + 1, sb);
            sb.deleteCharAt(sb.length() - 1); // 回溯
        }
    }
}