题解 | #字符串的排列#

#这题可以通过递归完成，但要注意去重的问题
class Solution:
    def Permutation(self , str: str) :
        # write code here
        def back(path,used):  #path用来记录当前的字符串
            if len(path)==k :   
			#记住这里不要加入上面if path  not in res来去重，对于多次递归来说，实在太慢了，尤其是res设置成列表的时候，每做依次判断，都要在列表里面遍历一遍，时间复杂度最多能能达到：（列表长度）*n!
                res.add(path)
                return

            for i in range(len(str)):
                if i>0 and str[i]==str[i-1] and used[i-1]==0:continue #这一句避免重复字符串（例如aab会输出两个aab），虽然做了结果做了去重，但直接从循环下手，也很省时间
                if used[i]:continue 
                used[i]=1  
				#这两句话主要为了判断元素是否被使用（例如：aab，第一个a被用了，used会变成[1,0,0]），将它带入下个递归时，循环语句就会自己跳过它，只遍历ab，最后输出aab,aba
                back(path+str[i],used)
				#开始递归
                used[i]=0 #这个循环用完了，记得把它改回来，不然在循环第二个used就会是【1，1，0】,那么最终只会输出了ab了

                
        res=set() #为了省去去重的麻烦，直接把res设置成集合，让它自己去去重，输出结果的时候再转回来就行了，反正结果不在乎顺序
        path=""
        k=len(str)
        back("",[0]*k)
        return list(res)