LeetCode 热题 100 17. 电话号码的字母组合-EW帮帮网

LeetCode 热题 100 | 17. 电话号码的字母组合

大家好，今天我们来解决一道经典的算法题——电话号码的字母组合。这道题在 LeetCode 上被标记为中等难度，要求给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。下面我将详细讲解解题思路，并附上 Python 代码实现。

问题描述

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

示例 1：

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

示例 2：

输入：digits = ""
输出：[]

示例 3：

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

提示：

0 <= digits.length <= 4
digits[i] 是范围 [‘2’, ‘9’] 的一个数字。

解题思路

核心思想

回溯法：
- 回溯法是一种通过递归枚举所有可能解的方法。
- 在生成字母组合的过程中，我们逐个选择数字对应的字母，并将其加入当前组合中。
递归终止条件：
- 当当前组合的长度等于数字字符串的长度时，说明已经生成了一个完整的字母组合，将其加入结果列表中。
递归过程：
- 遍历数字字符串中的每个数字，根据数字到字母的映射关系，选择对应的字母。
- 将当前选择的字母加入当前组合，并递归生成下一个数字的字母组合。
- 在递归返回时，移除当前组合中的最后一个字母（回溯）。

Python代码实现

class Solution:
    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        if not digits:
            return []
        
        phone = {
            '2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
            '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'
        }
        
        result = []
        path = []
        
        def backtracking(index):
            if index == len(digits):
                result.append(''.join(path))
                return
            
            for letter in phone[digits[index]]:
                path.append(letter)
                backtracking(index + 1)
                path.pop()
        
        backtracking(0)
        return result

# 测试示例
solution = Solution()

# 示例 1
digits1 = "23"
print(solution.letterCombinations(digits1))  # 输出: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]

# 示例 2
digits2 = ""
print(solution.letterCombinations(digits2))  # 输出: []

# 示例 3
digits3 = "2"
print(solution.letterCombinations(digits3))  # 输出: ["a", "b", "c"]

代码解析

回溯函数 backtracking：
- 参数：
  - index：当前递归的索引，用于遍历数字字符串。
- 当 index 等于数字字符串的长度时，说明已经生成了一个完整的字母组合，将其加入结果列表 result。
- 遍历当前数字对应的字母，将每个字母加入当前组合 path，并递归生成下一个数字的字母组合。
- 在递归返回时，移除 path 中的最后一个字母（回溯）。
结果列表 result：
- 用于存储所有生成的字母组合。
路径列表 path：
- 用于存储当前递归过程中正在构建的字母组合。
数字到字母的映射 phone：
- 用于将数字映射到对应的字母。

复杂度分析

时间复杂度：O(3^n * 4^m)，其中 n 是数字 2-6 的个数，m 是数字 7-9 的个数。每个数字 2-6 对应 3 个字母，每个数字 7-9 对应 4 个字母。
空间复杂度：O(n + m)，递归调用栈的深度为 n + m，同时需要存储当前字母组合 path。

示例运行

示例 1

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

示例 2

输入：digits = ""
输出：[]

示例 3

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

总结

通过回溯法，我们可以高效地生成电话号码的所有字母组合。这种方法利用递归枚举所有可能的字母组合，并通过回溯避免重复选择。希望这篇题解对大家有所帮助，如果有任何问题，欢迎在评论区留言讨论！

关注我，获取更多算法题解和编程技巧！

LeetCode 热题 100 17. 电话号码的字母组合