我来给你讲解 LeetCode 第 17 题「电话号码的字母组合」。

题目描述

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按任意顺序返回。

数字到字母的映射如下（与电话按键相同）：

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

示例：

• 输入：digits = "23"
• 输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

解题思路分析

第一步：理解问题本质

这个问题需要将数字字符串中的每个数字映射为对应的字母集合，然后生成所有可能的字母组合。这本质上是一个组合生成问题。

关键观察：

• 每个数字对应3-4个字母
• 需要生成所有可能的排列组合
• 组合长度等于输入数字字符串的长度

第二步：确定算法策略

这种"所有可能组合"的问题通常使用回溯法（深度优先搜索）来解决。回溯法的核心思想：

1. 尝试一个选择
2. 递归处理剩余部分
3. 撤销选择（回溯），尝试其他可能性

第三步：建立数字到字母的映射

首先我们需要建立数字到对应字母的映射关系：

digit_map = {
    '2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
    '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'
}

第四步：设计回溯函数

我们需要设计一个回溯函数，主要参数包括：

• index: 当前处理到的数字位置
• current: 当前已构建的字母组合
• result: 存储所有有效结果的列表

回溯函数的执行逻辑：

1. 终止条件：当 index == len(digits) 时，说明已经处理完所有数字，将当前组合加入结果
2. 遍历选择：对于当前数字对应的每个字母，依次尝试
3. 递归探索：选择当前字母后，递归处理下一个数字
4. 回溯：递归返回后，继续尝试下一个字母

第五步：完整算法实现

def letterCombinations(digits):
    if not digits:  # 处理空输入
        return []
    
    digit_map = {
        '2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
        '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'
    }
    
    result = []
    
    def backtrack(index, current):
        # 终止条件：已处理完所有数字
        if index == len(digits):
            result.append(''.join(current))
            return
        
        # 获取当前数字对应的字母
        digit = digits[index]
        letters = digit_map[digit]
        
        # 遍历当前数字的所有可能字母
        for letter in letters:
            current.append(letter)          # 做出选择
            backtrack(index + 1, current)   # 递归处理下一个数字
            current.pop()                   # 撤销选择（回溯）
    
    backtrack(0, [])
    return result

第六步：逐步演示执行过程

以输入 "23" 为例：

初始状态：index=0, current=[]

第一层循环（数字'2'，字母"abc"）：

• 选择'a'：current=['a'] → 递归处理下一个数字
  • 第二层循环（数字'3'，字母"def"）：
    • 选择'd'：current=['a','d'] → 到达终点，得到"ad"
    • 选择'e'：current=['a','e'] → 得到"ae"
    • 选择'f'：current=['a','f'] → 得到"af"
• 选择'b'：current=['b'] → 递归处理下一个数字
  • 同样得到"bd", "be", "bf"
• 选择'c'：current=['c'] → 递归处理下一个数字
  • 得到"cd", "ce", "cf"

最终结果：["ad","ae","af","bd","be","bf","cd","ce","cf"]

第七步：复杂度分析

• 时间复杂度：O(3ᴺ × 4ᴹ)，其中N是映射到3个字母的数字个数，M是映射到4个字母的数字个数
• 空间复杂度：O(N)，主要取决于递归调用栈的深度

第八步：关键要点总结

1. 回溯模板：选择 → 递归 → 撤销选择，这是回溯算法的经典模式
2. 终止条件：当处理完所有数字时保存结果
3. 边界处理：空输入需要特殊处理
4. 递归参数：index记录处理进度，current记录当前路径

这种解法清晰地展示了回溯算法的应用，是解决组合类问题的典型范例。