本文目录
- 1 中文题目
- 2 最优解法：迭代法
- 2.1 方法思路
- 2.2 Python代码
- 2.3 复杂度分析
- 3 题目总结
1 中文题目
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例：
输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
输入：digits = ""
输出：[]
输入：digits = "2"
输出：["a","b","c"]
提示：
- 0 ≤ d i g i t s . l e n g t h ≤ 4 0 \leq digits.length \leq 4 0≤digits.length≤4
- 2 ≤ d i g i t s [ i ] ≤ 9 2 \leq digits[i] \leq 9 2≤digits[i]≤9
2 最优解法：迭代法
2.1 方法思路
方法核心
每处理一个数字，就将当前所有可能的组合与这个数字对应的字母进行组合，得到新的所有可能组合。
实现步骤
- 初始化一个只包含空字符串的结果列表 result = []
- 遍历输入的每个数字，对于每个数字：
- 获取该数字对应的所有可能字母
- 将已有的每个组合与当前数字的每个字母进行拼接，形成新的组合
方法示例
以输入"23"为例说明过程：
- 处理’2’时：result = [] → [‘a’, ‘b’, ‘c’]
- 处理’3’时：[‘a’, ‘b’, ‘c’] → [‘ad’, ‘ae’, ‘af’, ‘bd’, ‘be’, ‘bf’, ‘cd’, ‘ce’, ‘cf’]
2.2 Python代码
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
# 处理空输入
if not digits:
return []
# 数字到字母的映射字典
digit_map = {
'2': 'abc',
'3': 'def',
'4': 'ghi',
'5': 'jkl',
'6': 'mno',
'7': 'pqrs',
'8': 'tuv',
'9': 'wxyz'
}
# 存储结果
result = ['']
# 遍历每个数字
for digit in digits:
# 临时列表存储新的组合
new_result = []
# 获取当前数字对应的字母
letters = digit_map[digit]
# 遍历现有的组合
for combo in result:
# 将当前数字对应的每个字母添加到现有组合中
for letter in letters:
new_result.append(combo + letter)
# 更新结果列表
result = new_result
return result
2.3 复杂度分析
- 时间复杂度：
O
(
4
n
)
O(4^n)
O(4n)，
n
n
n是输入数字的长度
- 每个数字最多对应 4 4 4个字母
- 每次迭代产生的组合数呈指数增长
- 空间复杂度：
O
(
4
n
)
O(4^n)
O(4n)
- 需要存储所有可能的组合
- 空间占用主要在结果列表
3 题目总结
题目难度：中等
数据结构：数组
应用算法：迭代法