题解 | #字符串的排列#

class Solution:
    def Permutation(self , str: str) -> List[str]:
        # write code here
        res = []
        path = ""
        n = len(str)
        vis = [0]*len(str)
        str = "".join((lambda x:(x.sort(),x)[1])(list(str)))
        def backtrack(path, s, n, vis):
            if len(path) == n:
                res.append(path)
                return 
            
            for i in range(len(str)):
                if vis[i] == 1:
                    continue
                
                if i > 0 and s[i-1] == s[i] and not vis[i-1]:
                    continue
                vis[i] = 1

                path = path + s[i]
                
                backtrack(path, s, n, vis)

                vis[i] = 0

                path = path[:-1]

        backtrack(path, str, n, vis)
        return res