回溯题解——电话号码的字母组合【LeetCode】

17. 电话号码的字母组合

✅ 一、算法逻辑讲解（每一步在做什么）

步骤逐行讲解：

1. MAPPING：

   • 字符串与电话按键的映射，数字 2～9 映射到相应字母。

   • 索引从 0 开始，为方便直接用数字下标查询。

2. letterCombinations(self, digits: str)：

   • 主函数，接收一个字符串 digits，如 "23"。

3. if n == 0: return []

   • 边界处理：空字符串直接返回空列表。

4. path = [''] * n

   • 用于构造当前组合路径（长度固定为输入长度 n），避免字符串拼接频繁生成新对象（效率优化）。

5. dfs(i)：

   • 从第 i 位开始，依次选择可能的字符，递归构建组合。

   • 终止条件是 i == n：所有位置都选好了，把路径拼接成字符串加入 ans。

6. for c in MAPPING[int(digits[i])]

   • 遍历当前数字对应的所有字符，例如 "2" → "abc"，每种可能都尝试一次。

7. path[i] = c + dfs(i+1)

   • 选择当前字符后进入下一位。

   • 每次只改变当前位置 i，路径的其他部分不变。

8. 最终返回 ans，包含所有合法组合。

⭐ 二、核心思路（算法关键点）

核心点是：DFS + 回溯，进行多叉树的全排列构造

• 这题等价于：从多个字符集合中，选择一个字符构成全排列
  举例：输入 "23" → 组合 "ad", "ae", "af", "bd", ...。

• 每一层 DFS 对应一个数字（一个位置），每一层会有 len(MAPPING[digit]) 个分支。

• 因为是每一位都必须选一个字符 → 无需回溯弹出，只需要在 path[i] 原地修改。

MAPPING = "", '', "abc", "def", "ghi", "jkl", "mno", "pqrs","tuv", "wxyz"

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        n = len(digits)
        if n == 0:
            return []
        ans = []
        path = [''] * n

        def dfs(i: int) -> None:
            if i == n:
                ans.append(''.join(path))
                return
            for c in MAPPING[int(digits[i])]:
                path[i] = c
                dfs(i + 1)

        dfs(0)
        return ans

⏱ 三、时间复杂度分析

时间复杂度：O(3^m * 4^n)

• 每个数字最多映射 4 个字母（最多的是 7 和 9）。

• 假设有 m 个数字映射 3 个字符（如 2、3、4、5、6、8），n 个数字映射 4 个字符（如 7、9），总共组合数量为：
  3^m * 4^n

• 对于每个组合，生成字符串的时间是 O(k)，k 是输入长度。但由于是原地数组 + join，实际很快。

• 举例：

  • 输入 "23"：总组合数是 3 × 3 = 9

  • 输入 "79"：4 × 4 = 16，总共16个组合

通常输入最多11位手机号，组合数也就几千个，DFS 是可以接受的。

💾 四、空间复杂度分析

空间复杂度：O(n)

• 递归栈深度最多为 n（每个字符位最多一次递归调用）。

• path 数组长度为 n，是构造路径用的。

输出空间：O(3^m * 4^n)（用于保存所有组合字符串）

如果不计输出结果空间，则辅助空间为 O(n)。