Interview question 08.08 Permutation with duplicate strings

topic

Interview questions 08.08. There are permutations and combinations of repeated strings
There are permutations and combinations of repeated strings . Write a method , Calculates all permutations of a string .

Example 1:

Input ：S = “qqe”
Output ：[“eqq”,“qeq”,“qqe”]
Example 2:

Input ：S = “ab”
Output ：[“ab”, “ba”]
Tips :

The characters are all English letters .
The string length is [1, 9] Between .

Their thinking

Add one set duplicate removal

Code

class Solution:
    def permutation(self, S: str) -> List[str]:
        return self.doIt(list(S), '')

    def doIt(self, s: List[str], pre: str) -> List[str]:
        size = len(s)
        if size == 1:
            return [pre + s[0]]
        ans = []
        have=set()
        for i in range(size):
            if s[0] not in have:
                have.add(s[0])
                ans += self.doIt(s[1:], pre + s[0])
            if i < size - 1:
                s[0], s[i + 1] = s[i + 1], s[0]
        return ans