38. 字符串的排列

题目链接：https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof/
难度：中等

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

题解

class Solution:
    def permutation(self, s: str) -> List[str]:
        chars = list(s)
        ret = []
        def dfs(x):
            if x == len(chars) - 1:
                ret.append("".join(chars))
                return
            char_set = set()
            for i in range(x, len(chars)):
                if chars[i] in char_set:
                    continue
                char_set.add(chars[i])
                chars[x], chars[i] = chars[i], chars[x]
                dfs(x+1)
                chars[x], chars[i] = chars[i], chars[x]
        dfs(0)
        return ret