LeetCode 17. 电话号码的字母组合是一道经典的回溯/笛卡尔积问题。核心思路是遍历每个数字对应的字母逐层组合。核心思路建立数字到字母的映射表手机九宫格对每个数字取出其对应的所有字母用迭代或回溯生成所有组合Python3 完整实现解法一迭代法推荐最直观class Solution:def letterCombinations(self, digits: str) - list[str]:if not digits:return []phone { 2: abc, 3: def, 4: ghi, 5: jkl, 6: mno, 7: pqrs, 8: tuv, 9: wxyz, } result [] for digit in digits: result [prev ch for prev in result for ch in phone[digit]] return result解法二回溯法class Solution:def letterCombinations(self, digits: str) - list[str]:if not digits:return []phone { 2: abc, 3: def, 4: ghi, 5: jkl, 6: mno, 7: pqrs, 8: tuv, 9: wxyz, } result [] def backtrack(index, path): if index len(digits): result.append(path) return for ch in phone[digits[index]]: backtrack(index 1, path ch) backtrack(0, ) return result解法三itertools.product最简洁from itertools import productclass Solution:def letterCombinations(self, digits: str) - list[str]:if not digits:return []phone { 2: abc, 3: def, 4: ghi, 5: jkl, 6: mno, 7: pqrs, 8: tuv, 9: wxyz, } letters [phone[d] for d in digits] return [.join(combo) for combo in product(*letters)]三种解法对比项目 迭代法 回溯法 itertools时间复杂度 O(4ⁿ · n) O(4ⁿ · n) O(4ⁿ · n)空间复杂度 O(4ⁿ) O(n) 递归栈 O(4ⁿ)可读性 ⭐⭐⭐ ⭐⭐⭐ ⭐⭐⭐ 最简洁面试推荐 ✅ 好讲思路 ✅ 通用模板 ❌ 依赖库函数其中 n 为 digits 长度4 是因为数字 7、9 各有 4 个字母是最坏情况。关键细节空输入直接返回 []题目要求输入为空时返回空列表不是 [“”]迭代法的核心每处理一个新数字就把已有组合与新数字的每个字母做笛卡尔积用列表推导式一行搞定回溯法的关键index 表示当前处理到第几个数字path 是当前已拼好的字符串到达末尾时收集结果product(letters)解包将列表展开为多个参数product(“abc”, “def”) 等价于求两个集合的笛卡尔积面试中迭代法最好讲清楚思路回溯法是最通用的模板适合扩展到更复杂的组合问题。这道题的逆题——给定字符串判断是否为有效罗马数字LeetCode 38要不要也用 Python 写一遍
