程序员面试金典 - 面试题 08.07. 无重复字符串的排列组合

题目难度: 中等

原题链接

今天继续更新程序员面试金典系列, 大家在公众号 算法精选 里回复 面试金典 就能看到该系列当前连载的所有文章了, 记得关注哦~

题目描述

无重复字符串的排列组合。编写一种方法，计算某字符串的所有排列组合，字符串每个字符均不相同。

示例 1:

• 输入：S = "qwe"
• 输出：["qwe", "qew", "wqe", "weq", "ewq", "eqw"]

示例 2:

• 输入：S = "ab"
• 输出：["ab", "ba"]

提示:

• 字符都是英文字母。
• 字符串长度在[1, 9]之间。

题目思考

1. 如何利用给定字符串的各个字符都不相同这一条件?

解决方案

思路

• 由于给定字符串的各个字符都不相同, 所以我们可以每次从中挑选一个还未用过的字符, 将其加入当前排列字符串中, 这样由于每次挑选的顺序不同, 最终形成的排列也各不相同
• 这就是典型递归的思想, 具体做法如下:
  1. 维护两个字符串, 分别代表当前剩余未使用的字符, 以及当前排列字符串
  2. 针对当前未使用的字符, 逐一遍历它们, 并将其追加到当前排列字符串中, 这样就保证了每个排列字符串的顺序各不相同
  3. 然后继续传入新的未使用字符和排列, 继续递归调用
  4. 最后当未使用字符为空时结束递归, 此时就形成了一个排列
• 下面的代码中有详细的注释, 方便大家理解

复杂度

• 时间复杂度 O(N!): N 个字符各不相同, 排列就有 N! 种
• 空间复杂度 O(N): 递归栈的消耗

代码

class Solution:
    def permutation(self, S: str) -> List[str]:
        # 简单递归
        res = []

        def perm(remain, cur):
            # remain是剩余字符串
            # cur是当前排列字符串
            if not remain:
                # 没有剩余字符串了, 将当前排列加入最终结果中
                # 因为S没有重复字符, 所以保证了最终每个排列字符串都各不相同
                res.append(cur)
                return
            for i, c in enumerate(remain):
                # 选择remain中的各个字符追加到cur中, 然后继续递归
                perm(remain[:i] + remain[i + 1 :], cur + c)

        # 初始时剩余字符串为整个S, 当前排列字符串为空
        perm(S, "")
        return res

大家可以在下面这些地方找到我~😊

我的 GitHub

我的 Leetcode

我的 CSDN

我的知乎专栏

我的头条号

我的牛客网博客

我的公众号: 算法精选, 欢迎大家扫码关注~😊