电话号码的字母组合

链接：https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/

解题思路：回溯

当题目涉及到“所有组合”，“全排列”这样的字眼时，我们就应该在第一时间想到使用回溯算法求解。

初始化：

1. String digits 为给定的输入字符串
2. int cur 为遍历输入字符串当前的索引值
3. List<String> res 为返回的结果集
4. 将电话号码中的数字字符与对应的字母字符串进行映射，初始化映射为 Map<Character, String> map

我们可以使用 Java9 提供的一种初始化不可变的 map 的方式：

static final Map<Character, String> map = Map.of(
    '2', "abc", 
    '3', "def", 
    '4', "ghi", 
    '5', "jkl",
    '6', "mno", 
    '7', "pqrs", 
    '8', "tuv", 
    '9', "wxyz"
);

回溯方法 backtrack 的方法签名：

private void backtrack(String digits,List<String> res,int cur,Map<Character,String> map)

算法流程：

• 当 cur == digits.length() 时，说明递归结束，直接 return。
• 当 cur == 0 时，我们直接将 digits.charAt(0) 数字对应的字符串的每一个字母都添加到结果集 res 中。
• 否则，我们将结果集的每一个字符串 s 依次取出，将 digits.charAt(cur) 数字对应的字符串的每一个字母组合到字符串 s 的后面，构成一个新的字符串并添回到结果集 res 中；循环完毕后，cur++。

流程示意图：

代码

class Solution {

    static final Map<Character, String> map = Map.of(
        '2', "abc", 
        '3', "def", 
        '4', "ghi", 
        '5', "jkl",
        '6', "mno", 
        '7', "pqrs", 
        '8', "tuv", 
        '9', "wxyz"
    );

    public List<String> letterCombinations(String digits) {
        List<String> res = new ArrayList<>();
        backtrack(digits,res,0,map);
        return res;
    }

    private void backtrack(String digits,List<String> res,int cur,Map<Character,String> map){
        if(cur == digits.length())
            return;
        if(cur == 0){
            String s = map.get(digits.charAt(cur));
            for(int i = 0; i < s.length(); i++){
                res.add(s.charAt(i) + "");
            }
        }else {
            String s = map.get(digits.charAt(cur));
            int size = res.size();
            for(int i = 0; i < size; i++){
                String s1 = res.remove(0);
                for(int j = 0;j < s.length(); j++){
                    res.add(s1 + s.charAt(j));
                }
            }
        }
        backtrack(digits,res,cur + 1,map);
    }
}

复杂度分析

• 时间复杂度

时间复杂度为 ，其中 p 是输入中对应 3个字母的数字的个数，q 是输入中对应 4 个字母的数字的个数，p+q 是输入数字的总个数。

• 空间复杂度

额外申请的哈希表与输入无关，因为我们使用了递归，递归深度为输入的长度 n，所以额外空间复杂度为 。