Python数据结构算法--电话号码的字母组合
程序员文章站
2022-04-15 23:21:27
1. 问题Leetcode原题地址给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。示例:2. 思路在本题中,主要就是每个按键可以有不同的选择,在每个节点,也就是按下的数字位置有多个选择,这样就可以先选择一个,之后弹出这个元素,再选择下一个。 def letterCombinations(self, digits: str) -> List[str]: if not digits: return [] num_s...
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
上一篇: SpringCloud瞎姬霸写