解法一：回溯算法
def letterCombinations(digits):
if not digits:
return []
# 定义数字与字母映射关系
phone_map = {
'2': ['a', 'b', 'c'],
'3': ['d', 'e', 'f'],
'4': ['g', 'h', 'i'],
'5': ['j', 'k', 'l'],
'6': ['m', 'n', 'o'],
'7': ['p', 'q', 'r', 's'],
'8': ['t', 'u', 'v'],
'9': ['w', 'x', 'y', 'z']
}
res = []
def backtrack(combination, next_digits):
# 当没有剩余数字时，将当前组合添加到结果列表中
if len(next_digits) == 0:
res.append(combination)
else:
# 获取当前数字对应的字母列表
letters = phone_map[next_digits[0]]
for letter in letters:
# 递归调用下一位数字的字母组合
backtrack(combination + letter, next_digits[1:])
backtrack('', digits)
return res解法二：队列（广度优先搜索）
from collections import deque
def letterCombinations(digits):
if not digits:
return []
# 定义数字与字母映射关系
phone_map = {
'2': ['a', 'b', 'c'],
'3': ['d', 'e', 'f'],
'4': ['g', 'h', 'i'],
'5': ['j', 'k', 'l'],
'6': ['m', 'n', 'o'],
'7': ['p', 'q', 'r', 's'],
'8': ['t', 'u', 'v'],
'9': ['w', 'x', 'y', 'z']
}
queue = deque()
queue.append('')
for digit in digits:
# 获取当前数字对应的字母列表
letters = phone_map[digit]
# 将队列中的字符串逐个取出并与当前数字的字母组合，再放回队列
while len(queue[0]) == idx:
combination = queue.popleft()
for letter in letters:
queue.append(combination + letter)
return list(queue)