// @Title: 电话号码的字母组合 (Letter Combinations of a Phone Number)
// @Author: qisiii
// @Date: 2024-09-19 21:56:07
// @Runtime: 0 ms
// @Memory: 41 MB
// @comment: 
// @flag: 
class Solution {
    private String[] enums = new String[] { "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };

    public List<String> letterCombinations(String digits) {
        List<String> result = new ArrayList<>();
        dfs(result, new StringBuilder(), digits.toCharArray(), 0);
        return result;
    }

    private void dfs(List<String> result, StringBuilder sb, char[] arr, int cur) {
        if (cur == arr.length) {
            if (sb.length() > 0) {
                result.add(sb.toString());
            }
            return;
        }
        String str = enums[arr[cur] - '2'];
        for (int i = 0; i < str.length(); i++) {
            sb.append(str.charAt(i));
            dfs(result, sb, arr, cur + 1);
            sb.deleteCharAt(sb.length() - 1);
        }
    }
}

// @Title: 电话号码的字母组合 (Letter Combinations of a Phone Number)
// @Author: qisiii
// @Date: 2024-04-13 16:14:20
// @Runtime: 6 ms
// @Memory: 41.3 MB
// @comment: 
// @flag: 
class Solution {
    static String[] temp = new String[] { "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };

    public List<String> letterCombinations(String digits) {
        List<String> result = new ArrayList<>();
        if (digits.length() <= 0) {
            return result;
        }
         doAction("",0, digits, result);
         return result;
    }

    public void doAction(String str,int i, String digits, List<String> result) {
        if (str.length() == digits.length()) {
            result.add(str);
            return;
        }
        for(char c:temp[digits.charAt(i)-'0'].toCharArray()){
            doAction(str+c,i+1,digits,result);
        }
    }
}

// @Title: 电话号码的字母组合 (Letter Combinations of a Phone Number)
// @Author: qisiii
// @Date: 2024-04-12 17:52:06
// @Runtime: 5 ms
// @Memory: 41.4 MB
// @comment: 
// @flag: 
class Solution {
    static String[] temp = new String[] { "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };

    public List<String> letterCombinations(String digits) {
        List<String> result = new ArrayList<>();
        if (digits.length() <= 0) {
            return result;
        }
        return doAction(digits);
    }

    public static List<String> doAction(String digits) {
        List<String> result = new ArrayList<>();
        if (digits.length() <= 1) {
            for (char c : temp[digits.charAt(0)-'0'].toCharArray()) {
                result.add(c + "");
            }
            return result;
        } else {
            List<String> tempList = doAction(digits.substring(1));
            String c=temp[digits.charAt(0)-'0'];
            for(char ch:c.toCharArray()){
                for(int i=0;i<tempList.size();i++){
                    result.add(ch+ tempList.get(i));
                }
            }
            return result;
        }
    }
}