38 字符串的排列

Lin2J
2021-07-21 / 0 评论 / 89 阅读
温馨提示:
本文最后更新于2021-07-21,若内容或图片失效,请留言反馈。

剑指 Offer 38. 字符串的排列

输入一个字符串,打印出该字符串中字符的所有排列。
你可以以任意顺序返回这个字符串数组,但里面不能有重复元素。

解题思路:

对于长度为 $N$ 的不重复字符串,它的排列方案有 $N!$ 种。

可以采取字符交换的方式,先固定第 $1$ 位、再固定第 $2$ 位、……、最后固定第 $n$ 位。如下图:

38-abc的排列

以 "acb" 为例子,来讲述生成过程的思路。

  1. 初始时字符数组为 {'a', 'b', 'c'} ,且所有的交换都是和本身以及后面的元素交换。
  2. 固定第 $1$ 位,第 $1$ 位固定为 a(代码中就是 a 和 a 位置交换),剩下的可操作字符串就是 "bc"。
  3. 固定第 $2$ 位,第 $2$ 位可以固定为 b 或者 c (代码中就是 b 和 b 交换位置,或者 b 和 c 交换位置)
    1. 假设 b 和 c 交换位置,那么第二位固定为 c,剩下的可操作字符串就是 "b"。
  4. 固定第 $3$ 位,第 $3$ 位只剩下一个 b 可以选择,因此整个过程结束。此时字符数组的内容就是 {'a', 'c', 'b'} 。

**如果后面的元素有重复的话,就不需要交换了,因为会产生一个重复的结果。**因此碰到重复的元素,要跳过。

这个过程实际是一个深度优先搜索+剪枝法的结合

dfs函数

传递参数: 当前固定位 $x$。

终止条件: 当 $x = len(c) - 1$ 时,表示 $x$已经时最后一个字符了,只有一种情况,因此将组合 $c$ 转化成字符串加入 $ans$ 列表。

递推工作:

  1. 初始化一个集合 $set$,用来排除重复的字符串。
  2. 将第 $x$ 位的字符与 $i$ $\in$ $[x, len(c) - 1]$ 的字符分别交换,然后进入下一层递归
    1. 剪枝:如果 $c[i]$ 在 $set$ 中,代表这个字符已经交换过了,跳过这个字符。
    2. 交换字符:将 $x$ 位置和 $i$ 位置的字符进行交换
    3. 下一层递归:将当前位置 $x + 1$ 作为参数,传递给下一层递归。
    4. 还原字符:将 $x$ 位置和 $i$ 位置的字符再进行一次交换。
    5. 将 $c[i]$ 加入到 $set$ 中,方便后面的剪枝。

代码:

List<String> ans = new ArrayList<>();
char[] chars;

public String[] permutation(String s) {
    chars = s.toCharArray();
    dfs(0);
    return ans.toArray(new String[0]);
}

private void dfs(int x) {
    if (x == chars.length) {
        ans.add(new String(chars));
        return;
    }
    HashSet<Character> set = new HashSet<>();
    for (int i = x; i < chars.length; i++) {
        if (set.contains(chars[i])) {
            // 剪枝
            continue;
        }
        swap(i, x);
        dfs(x + 1);
        swap(i, x);
        set.add(chars[i]);
    }
}

private void swap(int i, int j) {
    char tmp = chars[i];
    chars[i] = chars[j];
    chars[j] = tmp;
}

复杂度分析

  • 时间复杂度$O(N!N)$:$N$ 为字符串的长度,最坏情况下,所有字符都不相同,需要生成 $N!$ 个结果,每个结果都需要使用 $O(N)$ 的时间来拼接字符串。
  • 空间复杂度$O(N^2)$:$N$ 为字符串的长度,整个过程累计递归栈空间为 $O(N)$;每层递归中辅助集合存储的字符串数量最多为 $N + (N-1) + (N-2) + ... + 2 + 1 = \frac{(N+1)N}{2}$,及占用 $O(N^2)$ 的空间。