【经典LeetCode算法题目专栏分类】【第11期】递归问题:字母大小写全排列、括号生成

2023-12-23 18:59:31

??《博主简介》

小伙伴们好,我是阿旭。专注于人工智能AI、python、计算机视觉相关分享研究。
?更多学习资源,可关注公-仲-hao:【阿旭算法与机器学习】,共同学习交流~
👍感谢小伙伴们点赞、关注!

《------往期经典推荐------》

一、AI应用软件开发实战专栏【链接】
二、机器学习实战专栏【链接】,已更新31期,欢迎关注,持续更新中~~
三、深度学习【Pytorch】专栏【链接】
四、【Stable Diffusion绘画系列】专栏【链接】

递归

字母大小写全排列

class?Solution:

????def?letterCasePermutation(self,?S:?str)?->?List[str]:

????????def?DFS(s_list,?index):

????????????if?index ==?len(s_list):

????????????????res.append(''.join(s_list))

????????????????return?

????????????# 未修改当前字符(字母或者数字)的一条分支 ?

????????????DFS(s_list,?index +?1)?

????????????# 修改当前字母的的另一条分支

????????????if?s_list[index].isalpha():

????????????????s_list[index]?=?chr(ord(s_list[index])?^?32)

????????????????DFS(s_list,?index +?1)

????????res =?[]

????????S =?list(S)

????????DFS(S,?0)

????????return?res

#?回溯

class?Solution:

????def?permutation(self,?s:?str)?->?List[str]:

????????def?backtrack(s,?cur_s):

????????????if?len(cur_s)?==?len(s):

????????????????res.append(cur_s)

????????????????return

????????????for?i in?range(len(s)):

????????????????if?i >?0?and?s[i]?==?s[i-1]?and?visited[i-1]?==?False:

????????????????????continue

????????????????if?visited[i]?==?False:

????????????????????visited[i]?=?True

????????????????????backtrack(s,?cur_s +?s[i])

????????????????????visited[i]?=?False

????????res =?[]

????????visited =?[False?for?_ in?range(len(s))]

????????s =?''.join(sorted(list(s)))

????????backtrack(s,'')

????????return?res

22.括号生成

class?Solution:

????def?generateParenthesis(self,?n:?int)?->?List[str]:

????????res =?[]

????????def?generator(left,?right,?s):

????????????if?left ==?n and?right ==?n:

????????????????res.append(s)

????????????????return

????????????if?left <?n:

????????????????generator(left+1,?right,?s +?'(')

????????????if?left >?right:

????????????????generator(left,?right+1,?s +?')')

????????generator(0,0,'')

????????return?res

关于本篇文章大家有任何建议或意见,欢迎在评论区留言交流!

觉得不错的小伙伴,感谢点赞、关注加收藏哦!

欢迎关注下方GZH:阿旭算法与机器学习,共同学习交流~

文章来源:https://blog.csdn.net/qq_42589613/article/details/135171518
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。