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

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

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