题解 | #字符串的排列#

import copy
class Solution:
    def Permutation(self , str: str) -> list[str]:
        # write code here
        self.str_len = len(str)
        self.cand = []
        self._build('', str, 0)        
        return self.cand
    
    def _build(self, prefix, rem_str, length):
        if length == self.str_len:
            self.cand.append(prefix)
        vis = set()
        for i, ele in enumerate(rem_str):
            if ele in vis:
                continue
            else:
                vis.add(ele)
            self._build(prefix+ele, rem_str[:i]+rem_str[i+1:], length+1)

关键在于有重复元素的处理，原先我建立了hash字典，但是这样的字典在每一次递归时都会copy一次，超时。所以用了集合表示当前递归已经用过的元素。

所以尽量不要deepcopy