17.Letter Combinations of a Phone Number

17. Letter Combinations of a Phone Number

为什么电话号码字母组合的代码里不需要 onPath 数组，而全排列的代码却必须用，核心原因在于这两个问题的选择规则和元素来源完全不同。

核心差异分析

先明确两个问题的选择逻辑：

电话号码字母组合（letterCombinations）：
- 每个位置（第 i 位）的选择范围是固定且独立的：只和输入数字的第 i 位对应（比如数字 2 对应 abc，数字 3 对应 def）。
- 不同位置的选择互不干扰，且同一位置的字母不会重复选（比如第 0 位选了 a，第 1 位选 d，不存在 “重复选同一个元素” 的问题）。
- 本质是按位置依次选取固定集合中的元素，没有 “选过 / 没选过” 的状态需要记录。
全排列（permute）：
- 所有位置的选择范围都是同一个数组 nums，但要求每个元素只能选一次（比如 nums=[1,2,3]，第 0 位选了 1，后面就不能再选 1）。
- 本质是从同一集合中选不重复的元素填充位置，必须记录 “哪些元素已经被选过”，否则会出现重复（比如 [1,1,2] 这种无效排列）。

Solution:

python

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

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits:
            return []
        n = len(digits)
        path = [''] * n # 注意 path 长度一开始就是 n，不是空列表
        ans = []
        def dfs(i):
            if i == n: # 不是 n-1
                ans.append(''.join(path))
                return
            for c in MAPPING[int(digits[i])]:
                path[i] = c # 直接覆盖，不用恢复现场
                dfs(i + 1)
        dfs(0)
        return ans

复杂度分析

时间复杂度：O(n4^n)，其中 n 为 digits 的长度。最坏情况下每次需要枚举 4 个字母，递归次数为一个满四叉树的节点个数，那么一共会递归 O(4^n) 次（等比数列和），再算上加入答案时复制 path 需要 O(n) 的时间，所以时间复杂度为 O(n4^n)。
空间复杂度：O(n)。返回值的空间不计。