LeetCode 17. Letter Combinations of a Phone Number 题解题目描述给定一个仅包含数字2-9的字符串返回所有它能表示的字母组合。答案可以按任意顺序返回。给出数字到字母的映射如下与电话按键相同。注意 1 不对应任何字母。2: abc 3: def 4: ghi 5: jkl 6: mno 7: pqrs 8: tuv 9: wxyz示例 1输入digits 23 输出[ad,ae,af,bd,be,bf,cd,ce,cf]示例 2输入digits 输出[]示例 3输入digits 2 输出[a,b,c]解题思路方法回溯算法思路使用回溯算法生成所有可能的字母组合维护一个路径数组path来存储当前的组合维护一个索引index表示当前处理到的数字位置当index等于digits的长度时将path转换为字符串并添加到结果中否则获取当前数字对应的字母列表遍历每个字母将字母添加到path中递归调用回溯函数索引加 1回溯从path中移除字母复杂度分析时间复杂度O(4^n)其中 n 是输入数字的长度。每个数字最多对应 4 个字母因此总共有 4^n 种可能的组合。空间复杂度O(n)其中 n 是输入数字的长度。递归调用的栈空间和path数组的空间都是 O(n)。代码实现方法回溯算法class Solution: def letterCombinations(self, digits: str) - List[str]: if not digits: return [] # 数字到字母的映射 phone_map { 2: abc, 3: def, 4: ghi, 5: jkl, 6: mno, 7: pqrs, 8: tuv, 9: wxyz } result [] path [] n len(digits) def backtrack(index): # 当 index 等于 digits 的长度时将 path 转换为字符串并添加到结果中 if index n: result.append(.join(path)) return # 获取当前数字对应的字母列表 current_digit digits[index] letters phone_map[current_digit] # 遍历每个字母 for letter in letters: # 将字母添加到 path 中 path.append(letter) # 递归调用索引加 1 backtrack(index 1) # 回溯从 path 中移除字母 path.pop() backtrack(0) return result测试用例测试用例 1输入digits 23输出[ad,ae,af,bd,be,bf,cd,ce,cf]测试用例 2输入digits 输出[]测试用例 3输入digits 2输出[a,b,c]测试用例 4输入digits 7输出[p,q,r,s]总结本题是回溯算法的经典问题主要考察对回溯思想的理解和应用。通过维护一个路径数组和索引我们可以生成所有可能的字母组合。回溯算法的核心思想是通过选择、递归、回溯的过程遍历所有可能的解空间找到符合条件的解。在本题中我们需要注意以下几点建立数字到字母的映射表方便快速查找每个数字对应的字母。当处理完所有数字时将当前组合添加到结果中。对于每个数字遍历其对应的所有字母递归生成组合。这种方法不仅适用于电话号码的字母组合问题还可以应用于许多其他组合问题例如排列问题、组合问题等。掌握回溯算法的思想对于解决这类问题非常重要。