17. 电话号码的字母组合 - Letter Combinations of a Phone Number

🎯 问题描述（来源于LeetCode）

描述：
给定一个仅包含数字 2-9 的字符串 digits，返回所有它能表示的字母组合。答案可以按任意顺序返回。
数字到字母的映射如下（与电话按键相同）：

2: “abc”
3: “def”
4: “ghi”
5: “jkl”
6: “mno”
7: “pqrs”
8: “tuv”
9: “wxyz”

注意：1 不对应任何字母，0 也不对应。

说明：

输入字符串可能为空，此时返回空列表。

示例：

示例 1：

1 2	输入: digits = "23" 输出: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

示例 2：

1 2	输入: digits = "" 输出: []

示例 3：

1 2	输入: digits = "2" 输出: ["a","b","c"]

💻 解题思路

思路：回溯法（DFS）

算法步骤

定义全局映射字典或列表 MAPPING，将数字映射到对应的字母串（索引 0 和 1 为空字符串，方便直接通过 int(digit) 获取）。
如果 digits 为空，直接返回空列表。
初始化结果列表 ans 和路径列表 path（长度为 n，存储每个位置选择的字母）。
定义递归函数 dfs(i)：
- 如果 i == n，说明已处理完所有数字，将 path 拼接成字符串加入 ans，并返回。
- 否则，获取当前数字对应的所有可能字母：letters = MAPPING[int(digits[i])]。
- 遍历每个字母 c，将 path[i] 设为 c，然后递归调用 dfs(i+1)。
从 dfs(0) 开始搜索。
返回 ans。

代码实现

from typing import List

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):
            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(4^n \times n)$ ，其中 $n$ 是 digits 的长度。每个数字最多对应 4 个字母（如 7、9），因此组合数为 $O(4^n)$ ，每个组合需要 $O(n)$ 时间拼接。
空间复杂度： $O(n)$ ，递归栈深度为 $n$ ，加上路径数组 path 和结果存储（结果不计入空间复杂度）。