LeetCode 剑指 Offer 38. 字符串的排列

2022-08-25 HGNULB 约 5 分钟

文章信息 17 个分类 2 个标签

分类

LeetCode CodeTop 中等未解决 10-20 剑指 Offer 剑指 Offer（第 2 版）腾讯字节华为美团拼多多百度快手虾皮金山猿辅导

题目描述

✅ 剑指 Offer 38. 字符串的排列

题意分析

将字符串中的字符重新排列，返回全部不同的结果。每个字符出现的次数必须保持不变；交换两个相同字符不会产生新排列，因此不能只按字符下标枚举后直接收集。

解法：排序 + 回溯去重

核心思路

[!blue]

从左到右确定结果的每个位置。path 保存已经确定的前缀，used[idx] 表示输入中下标为 idx 的字符已经放入前缀。每层选择一个尚未使用的下标，路径长度达到 n 时便得到完整排列。

先排序，让相同字符相邻。若前一个相同字符还没使用，当前字符就跳过：本层选择这两个副本得到的字符相同，剩余字符也相同，会生成完全一样的排列。只保留靠前的副本，就能去掉这组重复分支。

若前一个相同字符已经在路径中，当前副本仍可使用，因为结果必须保留所有重复字符。这个规则相当于规定：相同字符始终按排序后的下标从小到大的顺序入路径。任意合法排列都能按这个顺序选出，因此不会漏解；每种排列又只有这一种下标选择顺序，因此不会重复。

收集答案时将路径复制为字符串。递归返回后同时撤销字符和 used 标记，使下一分支从相同的前缀状态开始。

解题步骤

将字符排序，初始化全为 false 的 used、空路径和结果列表。

进入递归后，若路径长度等于 n，保存当前字符串并返回。

枚举下标，跳过已使用的字符，以及前一个同值字符尚未使用的副本。

标记并加入当前字符，递归填写下一位置；返回后移除末尾字符，恢复标记。

代码实现

class Solution {
    public String[] permutation(String s) {
        char[] chars = s.toCharArray();

        Arrays.sort(chars);
        boolean[] used = new boolean[chars.length];
        List<String> res = new ArrayList<>();
        StringBuilder path = new StringBuilder();

        dfs(chars, used, path, res);

        return res.toArray(new String[0]);
    }

    private void dfs(char[] chars, boolean[] used, StringBuilder path, List<String> res) {
        if (path.length() == chars.length) {
            res.add(path.toString());

            return;
        }

        for (int idx = 0; idx < chars.length; idx++) {
            if (used[idx]) {
                continue;
            }

            // 前一个相同字符尚未入路径时，本层跳过当前副本；已经入路径时仍可继续使用。
            if (idx > 0 && chars[idx] == chars[idx - 1] && !used[idx - 1]) {
                continue;
            }

            used[idx] = true;
            path.append(chars[idx]);
            dfs(chars, used, path, res);
            // 路径与占用标记一起撤销，恢复后才能尝试同层其他选择。
            path.deleteCharAt(path.length() - 1);
            used[idx] = false;
        }
    }
}

import "sort"

func permutation(s string) []string {
    chars := []byte(s)
    sort.Slice(chars, func(i int, j int) bool {
        return chars[i] < chars[j]
    })

    used := make([]bool, len(chars))
    path := make([]byte, 0, len(chars))
    res := make([]string, 0)
    var dfs func()
    dfs = func() {
        if len(path) == len(chars) {
            res = append(res, string(path))
            return
        }

        for idx := 0; idx < len(chars); idx++ {
            if used[idx] {
                continue
            }
            // 前一个相同字符尚未入路径时，本层跳过当前副本；已经入路径时仍可继续使用。
            if idx > 0 && chars[idx] == chars[idx-1] && !used[idx-1] {
                continue
            }
            used[idx] = true
            path = append(path, chars[idx])
            dfs()
            // 路径与占用标记一起撤销，恢复后才能尝试同层其他选择。
            path = path[:len(path)-1]
            used[idx] = false
        }
    }
    dfs()
    return res
}

复杂度分析

时间复杂度：最坏为 $O(n \cdot n!)$，n 为字符串长度。字符互不相同时有 n! 个结果，每个结果需复制 n 个字符，排序的 $O(n\log n)$ 不影响总上界。

空间复杂度：$O(n)$（不计结果），来自递归栈、路径和 used；结果最坏占 $O(n \cdot n!)$。

关键点总结

[!green]

used 限制每个输入位置只使用一次，排序后的剪枝限制相同字符的使用顺序。

同层不重复选择同值字符，路径中仍允许出现多个相同字符。

路径达到原字符串长度才收集；全部字符相同时也会保留唯一排列。

易错点总结

[!yellow]

未排序就使用相邻剪枝，无法去掉原本不相邻的重复字符产生的分支。

剪枝条件缺少 !used[idx - 1]，会把路径中本应允许的第二个相同字符也剪掉。

回溯后漏恢复 used 或路径，会污染后续分支。

Go 若直接保存可变 []byte 路径会共享底层数组；转成 string(path) 再收集。

相似题目

题目	难度	关联与区别
46. 全排列	中等	不含重复值时无需同层去重，本题排序后按相同元素的使用次序剪枝。
90. 子集 II	中等	同样通过排序和选择顺序消除重复结果，但子集与排列对元素顺序的要求不同。

.article-image.is-loading { width: var(--article-image-width, 100%); height: auto; } .article-image.is-loading img { position: static; width: auto !important; height: auto !important; opacity: 1; pointer-events: auto; } .article-image-spinner { display: none; }

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2022/99472467

许可本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！