有重复字符串的排列组合.md

面试题 08.08. 有重复字符串的排列组合

https://leetcode-cn.com/problems/permutation-ii-lcci/

题目描述

有重复字符串的排列组合。编写一种方法，计算某字符串的所有排列组合。

示例1:

 输入：S = "qqe"
 输出：["eqq","qeq","qqe"]
示例2:

 输入：S = "ab"
 输出：["ab", "ba"]
提示:

字符都是英文字母。
字符串长度在[1, 9]之间。

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

思路

回溯
如果满足条件，就append到结果中
否则，就继续递归，找出

python代码

执行用时： 600 ms , 在所有 Python3 提交中击败了 12.57% 的用户 内存消耗： 15.2 MB , 在所有 Python3 提交中击败了 42.51% 的用户

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

        res=[]
        def backtrace(cur,rest):
            if(len(cur)==len(S) and cur not in res):
                res.append(cur)

            for idx in range(len(rest)):
                backtrace(cur+rest[idx],rest[:idx]+rest[1+idx:])
        
        backtrace('',S)
        return res