字符串的排列

字符串的排列_牛客题霸_牛客网

问题简述

输入一个长度为 n 字符串，打印出该字符串中字符的所有排列，你可以以任意顺序返回这个字符串数组。
例如输入字符串ABC,则输出由字符A,B,C所能排列出来的所有字符串ABC,ACB,BAC,BCA,CBA和CAB。

思路1：N叉树的前序遍历

• 排列的一般思路（假设无重复）：

  • 第 1 位有 n 种可能，固定第 1 位后第 2 位有 n-1 种可能、固定前 2 位后第 3 位有 n-2 种可能、...、固定前 n - 1 位后第 n 位有 1 种可能；

  • 即时间复杂度为 O(n!)，如果无法理解O(n!)的含义，就很可能写出错误的代码；

  • 具体来说，以 [1,2,3] 为例，第一位有 3 种可能，当固定第一位为 1 时，第二位有 [2,3] 两种可能，当固定第一位为 2 时，第二位依然有两种可能 [1,3]；

• 写法1）基于枚举（剪枝需要排序）

  • 使用一个全局变量记录已经用过的字符；

  • 去重方法：

    剑指 Offer 38. 字符串的排列 - 代码随想录

    • if i > 0 and s[i] == s[i - 1] and not used[i - 1]: continue；

• 写法2）基于交换（剪枝不需要排序）

  剑指 Offer 38. 字符串的排列（回溯法，清晰图解） - Krahets

  • 去重方法：在 dfs 内部记录使用过的字符；

• 写法 2 不需要排序，写起来也更简单；但是写法 1 可以返回字典序的排序，写法 2 做不到；

Python 写法1）基于枚举

class Solution:
    def Permutation(self , s: str) -> List[str]:
        
        N = len(s)
        s = sorted(list(s))
        used = [0] * N
        ret = []
        
        def dfs(d, tmp):
            if d == N: 
                ret.append(''.join(tmp[:]))
                return
            
            for i in range(N):
                # 基于树枝的剪枝
                # if i > 0 and s[i] == s[i - 1] and used[i - 1]:
                    # continue

                # 基于树层的剪枝（效率更高）
                if i > 0 and s[i] == s[i - 1] and not used[i - 1]:
                    continue

                if not used[i]:
                    used[i] = 1
                    tmp.append(s[i])
                    dfs(d + 1, tmp)
                    tmp.pop()
                    used[i] = 0
        
        dfs(0, [])
        return ret

Python 写法2）基于交换

class Solution:
    def Permutation(self, s: str) -> List[str]:

        n = len(s)
        s = list(s)
        ret = []

        def dfs(d):
            if d == n:
                ret.append(''.join(s))
                return

            book = set()  # 记录用过的字符（剪枝）
            for i in range(d, n):  # 遍历 s[d] 及之后的字符
                if s[i] not in book:
                    book.add(s[i])
                    s[d], s[i] = s[i], s[d]  # 交换
                    dfs(d + 1)
                    s[d], s[i] = s[i], s[d]  # 回溯
                    # book.remove(s[i])  # err，不需要清除标记

        dfs(0)
        return ret

思路2：下一个排列

• 先排序得到最小的字典序结果；

• 循环直到不存在下一个更大的排列；

• 下一个排列 思路：

  • 为了使下一个排列更大，一个方法是将一个左边的「较小数」与一个右边的「较大数」交换；

  • 而为了使变大的幅度最小，需要让这个「较小数」尽量靠右，而「较大数」尽可能小。

  • 实现起来并没有那么直观，详见代码；

Python

class Solution:
    def Permutation(self, s: str) -> List[str]:
        
        def next_permutation(a: List[str]) -> bool:
            N = len(a)

            # 从后向前查找第一个相邻顺序对 (i, i+1)，即满足 a[i] < a[i+1]；
            # 此时 `a[i+1:n)` 必为递减序列
            i = N - 2
            while i >= 0 and a[i] >= a[i + 1]:
                i -= 1

            if i < 0:  # i < 0，表示 a[0:n) 都是递减，即为最大排列
                return False
            else: 
                # 在 a[i+1:n) 中从后往前查找第一个 j 满足 a[i] < a[j]
                j = N - 1
                while j >= 0 and a[i] >= a[j]:
                    j -= 1
                # 至此，找到了 靠左的“较小数” 和 靠右的“较大数”，交换
                a[i], a[j] = a[j], a[i]

            # 将 a[i+1:n) 反转，此时 a[i+1:n) 必为递减序列；
            l, r = i + 1, N - 1
            while l < r:
                a[l], a[r] = a[r], a[l]
                l += 1
                r -= 1

            return True

        buf = sorted(s)
        ret = [''.join(buf)]
        while next_permutation(buf):
            ret.append(''.join(buf))

        return ret