(补)算法刷题Day21:BM58 字符串的排列

发布于:2024-12-22 ⋅ 阅读:(172) ⋅ 点赞:(0)

题目链接

描述
输入一个长度为 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次和无数次。


网站公告

今日签到

点亮在社区的每一天
去签到