package test20;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

/**
 * Desc:电话号码的字母组合
 * Author: YYB
 * Date: 2025/1/22
 * 思路：定义一个私有递归方法backtrack，这个方法的运作步骤是这样的，以处理数字串“23”为例
 * 先取出第一个数字字符‘2’，以及它对应的字符串“abc”，那么遍历字符串“abc”将得到三个递归：
 * backtrack("a", "3", phoneMap, combinations); 注：“3”指的是下一个要处理的数字
 * backtrack("b", "3", phoneMap, combinations);
 * backtrack("c", "3", phoneMap, combinations);
 * <p>
 * 注： backtrack("", “23”, phoneMap, combinations);开始时combination（结合体）是“”，遍历时也是“”+“a”=“a”，才得到上面三个递归
 * <p>
 * 以上三个递归方法每一个又要进行递归，以第一个为例
 * “3”对应“def”，然后遍历“def”
 * 所以backtrack("a", "3", phoneMap, combinations);又得到三个递归：
 * backtrack("ad", "", phoneMap, combinations);
 * backtrack("ae", "", phoneMap, combinations);
 * backtrack("af", "", phoneMap, combinations);
 * <p>
 * 由于nextDigits=“”符合if (nextDigits.length() == 0)条件，因此当要递归backtrack("ad", "", phoneMap, combinations);时，立马终止并把“ad”给add到集合
 * 然后是添加“ae”,"af"，所以a对应的三个组合字符串给添加到集合了
 * 以此类推添加b对应的三个和c对应的三个
 * 最后输出结果
 */
public class test17 {
    public static List<String> letterCombinations(String digits) {
        //先定义hashmap集合，将数字和相应的字符串以键值对存入,注：输入的是字符串形式的数字组合，后续要提取单个字符要用到charAt方法，所以用Character类型的key
        HashMap<Character, String> phoneMap = new HashMap<>();
        phoneMap.put('2', "abc");
        phoneMap.put('3', "def");
        phoneMap.put('4', "ghi");
        phoneMap.put('5', "jkl");
        phoneMap.put('6', "mno");
        phoneMap.put('7', "pqrs");
        phoneMap.put('8', "tuv");
        phoneMap.put('9', "wxyz");

        //然后用arrayList存每个组合
        ArrayList<String> combinations = new ArrayList<>();
        //先排除输入的字符串为null和空集合
        if (digits == null || digits.length() == 0) {
            return combinations;
        }
        //然后调用递归方法backtrack
        backtrack("", digits, phoneMap, combinations);
        return combinations;
    }

    //那就先把backtrack方法给定义好
    public static void backtrack(String combination, String digits, HashMap<Character, String> phoneMap, ArrayList<String> combinations) {
        //想要继续递归就先判断String digits是否因为递归变成了“”，说明没有数字可以处理了，则将String combination加到ArrayList<String> combinations集合
        if (digits.isEmpty()) {
            combinations.add(combination);
        } else {
            //否则继续递归，先提取索引为0的第一个数字以及对应的字符串，将字符串进行遍历
            char digit = digits.charAt(0);
            String letters = phoneMap.get(digit);
            //开始遍历字符串
            for (int i = 0; i < letters.length(); i++) {
                //得到字符串的每一个字符
                String letter = letters.substring(i, i + 1);
                //然后结合上面的例子，得到一个字符就相加再递归，然后待处理数字串去掉首位
                backtrack(combination + letter, digits.substring(1), phoneMap, combinations);
            }
        }
    }

    //测试用例
    public static void main(String[] args) {
        System.out.println(letterCombinations("23"));
        System.out.println(letterCombinations("356"));
    }
}