描述
输入一个长度为 n 字符串,打印出该字符串中字符的所有排列,你可以以任意顺序返回这个字符串数组。
例如输入字符串ABC,则输出由字符A,B,C所能排列出来的所有字符串ABC,ACB,BAC,BCA,CBA和CAB。
要求:空间复杂度 O(n!) 时间复杂度 O(n!)
思路:
方法一:
重点是避免重复遍历相同元素,因此一开始就对字符串进行排序,把相同元素的放在一起。同一元素只遍历一次。
方法二:
抄捷径,使用排列的库permutations
, 三行代码搞定。。。
# 方法一
import copy
result = []
def traverse(strr,path, used):
if len(path) == len(strr):
tmp = "".join(path)
result.append(tmp)
return
for i in range(len(strr)):
if i > 0 and strr[i] == strr[i-1] and not used[i-1]:
continue
if not used[i]:
used[i] = True
path.append(strr[i])
traverse(strr, path, used)
used[i] = False
path.pop()
class Solution:
def Permutation(self , strr: str) -> List[str]:
#先按字典序排序,使重复字符串相邻
strr = "".join((lambda x:(x.sort(), x)[1])(list(strr)))
used = [False for _ in range(len(strr))]
traverse(strr, [], used)
# result = permutations(list(strr),len(strr))
# result =list(set([''.join(x) for x in result]))
# print(result)
return result
# 方法二
from itertools import combinations,permutations
class Solution:
def Permutation(self , strr: str) -> List[str]:
result = permutations(list(strr),len(strr))
result =list(set([''.join(x) for x in result]))
return result
生病补卡,补卡这个东西和出g一样,只有0次和无数次。