字符串的排列（全排列）

问题简述

输入一个字符串，打印出该字符串中字符的所有排列。

详细描述

输入一个字符串，打印出该字符串中字符的所有排列。

你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。

示例:
    输入：s = "abc"
    输出：["abc","acb","bac","bca","cab","cba"]

限制：
    1 <= s 的长度 <= 8

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路1：DFS树状遍历+剪枝

• 深度优先求全排列的过程实际上相当于是一个多叉树的先序遍历过程；

  • 假设共有 n 种状态都不重复，则：

  • 第一层有 n 种选择；

  • 第二层有 n - 1 种选择；

  • ...

  • 共有 n! 种可能；

本题的难点是如何过滤重复的状态

• 写法1） 遍历所有状态，直接用 set 保存结果（不剪枝）：

• 写法2） 跳过重复字符（需排序）：

  • 其中用于剪枝的代码不太好理解，其解析详见：「代码随想录」剑指 Offer 38. 字符串的排列

    if not visited[i - 1] and i > 0 and s[i] == s[i - 1]: 
        continue

• 写法3） 在每一层用一个 set 保存已经用过的字符（不排序）：

• 写法2） 原地交换

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

  • 这个写法有点像“下一个排列”，只是没有使用字典序；

思路2：下一个排列

字符串的排列

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

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

Python

class Solution:
    def permutation(self, s: str) -> List[str]:
        
        def nextPermutation(nums: List[str]) -> bool:
            i = len(nums) - 2
            while i >= 0 and nums[i] >= nums[i + 1]:
                i -= 1

            if i < 0:
                return False
            else:
                j = len(nums) - 1
                while j >= 0 and nums[i] >= nums[j]:
                    j -= 1
                nums[i], nums[j] = nums[j], nums[i]

            left, right = i + 1, len(nums) - 1
            while left < right:
                nums[left], nums[right] = nums[right], nums[left]
                left += 1
                right -= 1

            return True

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

        return ret