题解 | 字符串的排列

学习完本题的思路你可以解决如下题目：

BM55. 没有重复项数字的全排列

BM56. 有重复项数字的全排列

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param str string字符串 
# @return string字符串一维数组
#
class Solution:
    def Permutation(self , str: str) -> List[str]:
        # write code here
        s, ans = list(str), []#字符串转化为数组方便操作，存储结果的列表
        def dfs(x):
            if x==len(s)-1:#下标为n-1时，所有位数已经固定完毕
                ans.append(''.join(s[:]))#把当前结果转化为字符串存储到结果列表
                return
            dic = set()#存储已经出现过的值
            for i in range(x,len(s)):
                if s[i] in dic:#如果当前值已经被固定过了，则直接跳过
                    continue
                dic.add(s[i])#将当前值放入出现过的集合
                s[i], s[x] = s[x], s[i]#固定第i位
                dfs(x+1)#进行回溯
                s[i], s[x] = s[x], s[i]#返回第i位
        dfs(0)#从下标0开始回溯
        return ans