字符串的排列.md

剑指 Offer 38. 字符串的排列

https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof/

题目描述

输入一个字符串，打印出该字符串中字符的所有排列。

 

你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。

 

示例:

输入：s = "abc"
输出：["abc","acb","bac","bca","cab","cba"]
 

限制：

1 <= s 的长度 <= 8

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

回溯
满足条件跳出递归
否则继续递归

python代码

执行用时： 8656 ms , 在所有 Python3 提交中击败了 5.02% 的用户 内存消耗： 20.5 MB , 在所有 Python3 提交中击败了 21.40% 的用户

class Solution:
    def permutation(self, s: str) -> List[str]:

        res=[]
        def backtrace(cur,rest):
            #满足条件，跳出递归
            if(len(cur)==len(s)):
                if(''.join(cur) not in res):
                    res.append(''.join(cur))
            #长度不满足条件，继续找
            for i in range(len(rest)):
                backtrace(cur+[rest[i]],rest[:i]+rest[1+i:])
        
        backtrace([],list(s))
        res=list(set(res))
        return res