# # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # # @param str string字符串 # @return string字符串一维数组 # 参考: https://blog.csdn.net/YouMing_Li/article/details/114521466 class Solution: # 超时 def Permutation1(self , str: str) -> List[str]: # write code here #字符串转为数组 n=len(str) arr=list(str) res=[] def backtrack(first=0): if n ==first: temp=arr.copy() st="".join(temp) if st not in res: res.append(st) for i in range(first,n): arr[first],arr[i]=arr[i],arr[first] backtrack(first+1) arr[first],arr[i]=arr[i],arr[first] # 先排序 #arr.sort() backtrack(0) #res.sort() return res def Permutation2(self , str: str) -> List[str]: # write code here #字符串转为数组 n=len(str) arr=list(str) res=[] def backtrack(arr,start=0): if n-1 ==start: st="".join(arr) if st not in res: res.append(st) return st=set() for i in range(start,n): if arr[i] in st: #跳过已经交换的字符 continue st.add(arr[i]) arr[start],arr[i]=arr[i],arr[start] backtrack(arr,start+1) arr[start],arr[i]=arr[i],arr[start] # 先排序 arr.sort() backtrack(arr) #res.sort() return res def Permutation(self , str: str) -> List[str]: # write code here #字符串转为数组 n=len(str) arr=list(str) res=[] isvisited=[False]*n def backtrack (arr:list,path:list,isvisited:list): if len(arr)==len(path): st="".join(path.copy()) res.append(st) return for i in range(n): if i>0 and arr[i]==arr[i-1] and not isvisited[i-1]: #跳过相同字符 continue if not isvisited[i]: # 未访问过 path.append(arr[i]) isvisited[i]=True backtrack(arr,path,isvisited) path.pop() isvisited[i]=False # 先排序 arr.sort() backtrack(arr,[],isvisited) #res.sort() return res