17-电话号码的字母组合

/**
电话号码的字母组合:17
2026-10-05 17:58:20
//给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。 
//
// 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。 
//
// 
//
// 
//
// 示例 1： 
//
// 
//输入：digits = "23"
//输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
// 
//
// 示例 2： 
//
// 
//输入：digits = "2"
//输出：["a","b","c"]
// 
//
// 
//
// 提示： 
//
// 
// 1 <= digits.length <= 4 
// digits[i] 是范围 ['2', '9'] 的一个数字。 
// 
//
// Related Topics 哈希表 字符串 回溯 👍 3311 👎 0

**/

//leetcode submit region begin(Prohibit modification and deletion)
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;

import java.util.Map;
import java.util.List;

class Solution {
     static Map<Character,List<Character>> map = new HashMap<Character, List<Character>>();

     static {
         map.put('2', Arrays.asList('a','b','c'));
         map.put('3', Arrays.asList('d','e','f'));
         map.put('4', Arrays.asList('g','h','i'));
         map.put('5', Arrays.asList('j','k','l'));
         map.put('6', Arrays.asList('m','n','o'));
         map.put('7', Arrays.asList('p','q','r','s'));
         map.put('8', Arrays.asList('t','u','v'));
         map.put('9', Arrays.asList('w','x','y','z'));
     }
    /**
     * 思路 回溯：
     *
     * 解答成功:
     *  执行耗时:1 ms,击败了51.16% 的Java用户
     *  内存消耗:43.1 MB,击败了16.49% 的Java用户
     * 时间复杂度： O(3^m * 4^n) m是3个字母的个数，n是4个字母的个数
     * 空间复杂度：3^m × 4^n × L
     * @param digits
     * @return
     */
    public List<String> letterCombinations(String digits) {
        if (digits == null || digits.length() == 0) {
            return null;
        }
        List<String> res = new ArrayList<>();
        huishu(res,digits,new StringBuilder());
        return res;

    }

    public void huishu(List<String> res , String s, StringBuilder sb) {
        if(sb.length() == s.length()) {
            res.add(sb.toString());
            return;
        }
        for(Character c: map.get(s.charAt(sb.length()))) {
            sb.append(c);
            huishu(res, s, sb);
            sb.deleteCharAt(sb.length() - 1);
        }
    }
}
//leetcode submit region end(Prohibit modification and deletion)