企业官网建设流程全解析

LeetCode 17. 电话号码的字母组合是一道经典的回溯/笛卡尔积问题。核心思路是：遍历每个数字对应的字母，逐层组合。

核心思路

1. 建立数字到字母的映射表（手机九宫格）
2. 对每个数字，取出其对应的所有字母
3. 用迭代或回溯生成所有组合

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 product

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', } 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 写一遍？