机试刷题_字符串的排列【python】

题目：字符串的排列

from os import dup
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param str string字符串 
# @return string字符串一维数组
#
class Solution:def backtrack(self,res,state,choices,selected):# 当状态长度等于元素数量时，记录解if len(state)==len(choices):res.append(state)returndupilcate = set()for i in range(len(choices)):# 剪枝：不允许重复选择元素，且不允许重复选择相等元素if not selected[i] and choices[i] not in dupilcate:#记录选择过的值dupilcate.add(choices[i])selected[i] = Truestate  += choices[i]# 进行下一轮选择self.backtrack(res,state,choices,selected)# 回退：撤销选择，恢复到之前的状态selected[i] = Falsestate = state[:-1]def Permutation(self , str: str) -> List[str]:res = []if len(str)==0:return restmp = "".join(sorted(list(str)))self.backtrack(res,state ="",choices = tmp,selected=[False]*len(tmp))return res