Leetcode字符串的排列

在这里插入图片描述

其实可以看成使用其中一个字符加上其他字符的连接，最后用set去重

class Solution:
    @lru_cache(None)
    def permutation(self, s: str) -> List[str]:
        if not s: return ['']
        res = set()
        for i in range(len(s)):
            for j in self.permutation(s[:i]+s[i+1:]):
                res.add(s[i]+j)
        return list(res)

题解链接：https://leetcode.cn/problems/zi-fu-chuan-de-pai-lie-lcof/solution/by-ke-ke-tub-llpt/

其他解法：
相当于每次固定前x位，交换之后的字符串，直到达到长度要求，也是需要通过判断去重

class Solution:
    def permutation(self, s: str) -> List[str]:
        c, res = list(s), []
        def dfs(x):
            if x == len(c) - 1:
                res.append(''.join(c))   # 添加排列方案
                return
            dic = set()
            for i in range(x, len(c)):
                if c[i] in dic: continue # 重复，因此剪枝
                dic.add(c[i])
                c[i], c[x] = c[x], c[i]  # 交换，将 c[i] 固定在第 x 位
                dfs(x + 1)               # 开启固定第 x + 1 位字符
                c[i], c[x] = c[x], c[i]  # 恢复交换
        dfs(0)
        return res