输入一个长度为 n 字符串，打印出该字符串中字符的所有排列，你可以以任意顺序返回这个字符串数组。

例如输入字符串ABC,则输出由字符A,B,C所能排列出来的所有字符串ABC,ACB,BAC,BCA,CBA和CAB。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param str string字符串 
# @return string字符串一维数组
#
class Solution1:
    def Permutation(self , str: str) -> List[str]:
        is_chose = [False]*len(str)
        self.choices = sorted([ch for ch in str])
        res = []
        self._back_trace('',is_chose=is_chose,res=res)
        return res 
    
    def _back_trace(self,cur_str:str,is_chose:list,res:list[str])->None:
        if len(cur_str)==len(self.choices):
            res.append(cur_str)
            return
        for i,choice in enumerate(self.choices):
            if is_chose[i] == False:
                if i >=1 and self.choices[i - 1] == self.choices[i] and not is_chose[i - 1]:
                    continue
                cur_str = cur_str+ choice
                is_chose[i] = True
                self._back_trace(cur_str,is_chose,res)
                is_chose[i] = False
                cur_str = cur_str[:-1]

为了去重：最开始排序choices即字符序列中的字符，然后当前的元素str[i]与同一层的前几个元素str[i-？]相同且str[i-？]已经用过了就需要跳过，换句话是如果前面一个是相同元素且没有用过则跳过

前面没用过，

错误写法：

1
2
if  i-1>=0 and self.choices[i-1]==self.choices[i] and is_chose[i-1]==True:
                   continue
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param str string字符串 
# @return string字符串一维数组
#
class Solution2:
    def Permutation(self , str: str) -> List[str]:
        is_chose = [False]*len(str)
        self.choices = sorted([ch for ch in str])
        res = []
        self._back_trace('',is_chose=is_chose,res=res)
        return list(set(res)) 
    
    def _back_trace(self,cur_str:str,is_chose:list,res:list[str])->None:
        if len(cur_str)==len(self.choices):
            res.append(cur_str)
            return
        for i,choice in enumerate(self.choices):
            if is_chose[i] == False:
                if  i-1>=0 and self.choices[i-1]==self.choices[i] and is_chose[i-1]==True:
                    continue
                # if i >=1 and self.choices[i - 1] == self.choices[i] and not is_chose[i - 1]:
                #     continue
                cur_str = cur_str+ choice
                is_chose[i] = True
                self._back_trace(cur_str,is_chose,res)
                is_chose[i] = False
                cur_str = cur_str[:-1]