回溯算法 17. 电话号码的字母组合

输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

输入：digits = ""
输出：[]

输入：digits = "2"
输出：["a","b","c"]

0 <= digits.length <= 4
digits[i] 是范围 ['2', '9'] 的一个数字。

public static List<String> letterCombinations(String digits) {
    if ("".equals(digits)) {
        return new ArrayList<>(0);
    }
    List<String> rsList = new ArrayList<>((int) Math.pow(3, digits.length()));
    Map<Character, List<Character>> map = Map.of(
            '2', List.of('a', 'b', 'c'), '3', List.of('d', 'e', 'f'),
            '4', List.of('g', 'h', 'i'), '5', List.of('j', 'k', 'l'),
            '6', List.of('m', 'n', 'o'), '7', List.of('p', 'q', 'r', 's'),
            '8', List.of('t', 'u', 'v'), '9', List.of('w', 'x', 'y', 'z')
    );
//        例：digits = "2"
    generateString(digits, 0, rsList, map, new StringBuilder());
    return rsList;
}

private static void generateString(String str, int p, List<String> list, Map<Character, List<Character>> map, StringBuilder sb) {
    if (p == str.length()) {
        list.add(sb.toString());
        return;
    }
//        'a', 'b', 'c'
    for (Character ch : map.get(str.charAt(p))) {
//            1. a
//            2. b
//            3. c
        sb.append(ch);
//            递归进入 p == 1   str.len == 1
//            toString加入集合后返回
        generateString(str, p + 1, list, map, sb);
//            1. 删除a
//            2. 删除b
//            3. 删除c
        sb.deleteCharAt(p);
    }
}