题目描述

输入一个字符串，打印出该字符串中字符的所有排列。
你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。

思路：dfs

定义一个set保持在当前位置已经访问过的字符

class Solution:
    def Permutation(self, s):
        def bfs(visited, unvisited):
            if len(unvisited) == 0:
                res.append(visited)
                return 
            d = set()
            for i, x in enumerate(unvisited):
                if x not in d:
                    d.add(x)
                    bfs(visited+x, unvisited[:i]+unvisited[i+1:])

        res = []
        bfs('', s)
        return res

print(Solution().Permutation('aab'))