2.算法-递归和回溯

回溯经典例题

https://zhuanlan.zhihu.com/p/112926891

39. 组合总和

def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        def backtrack(lst,target,res,path,begin,size):
            #step1:不满足条件直接返回
            if target<0: return 
            #step2:满足条件返回结果(执行一些操作)
            if target==0:
                res.append(path)
                return
            #step3:循环遍历所有的可能性
            for index in range(begin,size):
                backtrack(lst,target-lst[index],res,path+[lst[index]],index,size)
        size=len(candidates)
        if not size: return []
        res,path=[],[]
        backtrack(candidates,target,res,path,0,size)
        return res

140. 单词拆分 II

def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        import functools
        if not wordDict:return []
        wordDict = set(wordDict) #set 内部是dict实现 in操作时间复杂度O(1)
        max_len = max(map(len, wordDict)) # 高级写法
        @functools.lru_cache(None)
        def backtrack(s):
            res = []
            if not s:
                res.append("")
                return res
            for i in range(len(s)):
                if i < max_len and s[:i+1] in wordDict: 
                    for t in backtrack(s[i+1:]):
                        if not t:
                            res.append(s[:i+1])
                        else:
                            res.append(s[:i+1] + " " + t) #最后回溯的放在后面
            return res    
        return backtrack(s)

14. 自由之路

def findRotateSteps(self, ring: str, key: str) -> int:
        @lru_cache(None)
        def dfs(path,s):
            # 如果递归深度和key长度相同，递归结束
            if path == len(key):
                return 0

            left = s.find(key[path])
            left_str = s[left:]+s[:left]
            
            right = s.rfind(key[path])
            right_str = s[right:]+s[:right]

            left_res = dfs(path+1,left_str)
            right_res =  dfs(path+1,right_str)

            res = min(left+left_res,len(s)-right+right_res)+1
            return res
            
        return dfs(0,ring)

4. 17. 电话号码的字母组合

def letterCombinations(self, digits: str) -> List[str]:
        # 回溯 时间复杂度 3**a * 4**b  a,b表示字符串中对应字典值长度为3和4的数字个数
        if not digits: return []
        a = '23456789'
        b = ['abc','def','ghi','jkl','nmo','pqrs','tuv','wxyz']
        dic = dict(zip(a,b)) # 创建字典
        res,state = [],[] # 结果集/中间状态集
        def backtrack(idx):
            if idx == len(digits): 
                res.append("".join(state))
            else:
                num = digits[idx]
                for c in dic[num]:
                    state.append(c) # 更新状态
                    backtrack(idx+1) # 每次加入新字母后递归下一个位置
                    state.pop() # 清空状态
        backtrack(0)
        return res