LeetCode 电话号码的字母组合题解
LeetCode 电话号码的字母组合题解
题目描述
给定一个包含数字 2-9 的字符串，返回所有它能表示的字母组合。
示例：
输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
解题思路
方法：回溯
思路：
- 使用回溯算法来解决这个问题。
- 首先建立一个数字到字母的映射表。
- 从第一个数字开始，尝试所有可能的字母：
- 选择当前数字对应的字母，加入路径。
- 递归处理下一个数字。
- 回溯：撤销选择，继续尝试其他字母。
- 当路径长度等于数字字符串长度时，将路径加入结果列表。
复杂度分析：
- 时间复杂度：O(4^n * n)，其中 n 是数字字符串的长度。每个数字最多对应 4 个字母。
- 空间复杂度：O(n)，递归调用栈的深度为 n。
代码实现
方法：回溯
# 电话号码的字母组合（回溯） def letter_combinations(digits): if not digits: return [] phone_map = { '2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl', '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz' } result = [] path = [] def backtrack(index): if index == len(digits): result.append(''.join(path)) return digit = digits[index] for letter in phone_map[digit]: path.append(letter) backtrack(index + 1) path.pop() backtrack(0) return result # 测试 def test_letter_combinations(): digits = "23" print(letter_combinations(digits)) # 输出：['ad', 'ae', 'af', 'bd', 'be', 'bf', 'cd', 'ce', 'cf'] if __name__ == "__main__": test_letter_combinations()测试用例
测试用例 1：基本情况
输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
测试用例 2：空字符串
输入：digits = ""
输出：[]
总结
电话号码的字母组合是一个经典的回溯算法问题，它可以通过回溯算法来高效地解决。
回溯算法的核心思想是：从第一个数字开始，尝试所有可能的字母，递归处理下一个数字，然后撤销选择。
掌握回溯算法的使用方法，对于解决类似的问题非常重要。