我要评论1. 问题
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
示例：
2. 思路
在本题中，主要就是每个按键可以有不同的选择，在每个节点，也就是按下的数字位置有多个选择，这样就可以先选择一个，之后弹出这个元素，再选择下一个。
def letterCombinations(self, digits: str) -> List[str]:
if not digits:
return []
num_str = {
'2':'abc',
'3':'def',
'4':'ghi',
'5':'jkl',
'6':'mno',
'7':'pqrs',
'8':'tuv',
'9':'wxyz'
}
res = []
path = []
def comb(index):
if index == len(digits):
res.append(''.join(path))
return
for char in num_str[digits[index]]:
path.append(char)
comb(index+1)
path.pop()
comb(0)
return res
3. 总结
回溯问题，总结框架
def permute(nums):
res = [] # 结果：保存结果路径
track = [] # 路径：记录在 track 中
def backtrack(nums, track):
if 结束条件：
res.append(track[:])
return
for i in 可选择的选项:
track.append(i) # 做选择
backtrack(nums[1:], track) # 进入下一层决策树
track.pop() # 取消选择
backtrack(nums, track)
return res
本文地址：https://blog.csdn.net/weixin_42165585/article/details/108237686
如您对本文有疑问或者有任何想说的，请点击进行留言回复，万千网友为您解惑！
网友评论