BM58　字符串的排列¶

中等通过率 23.58%python3核心代码模式样例通过牛客 AC字符串递归

牛客原题　源码

讲解章节：DFS 深度优先搜索

一句话

先排序让相同字符相邻，回溯时「同层跳过重复字符」去重。

解题思路¶

这题考什么¶

全排列的骨架是「逐位决定」：第 1 位从所有未用字符里挑一个，第 2 位从剩下的里挑，挑满 n 位就得到一个排列，回溯换下一个选择。

难点全在去重上：输入可能有重复字符（"aab"），朴素做法会把两个 'a' 当成不同的东西，产出 3! = 6 个结果，其中一半彼此重复。

去重的标准手法是「排序 + 同层剪枝」：先把字符排序，相同字符必然相邻；填某一位时，如果当前字符与前一个字符相同，而前一个字符在本层还没被用掉，说明它是刚刚回溯撤销的那个分支，再选当前这个只会产出完全一样的排列，直接跳过。

a a b        第 1 位选下标 0 的 a  -> 展开 "a|ab"、"a|ba"
^ ^          第 1 位选下标 1 的 a  -> used[0] 为假 -> 剪掉（否则又是同样两串）
             第 1 位选 b          -> 展开 "b|aa"

这条规则保证「每种字符在每一层只被选一次」，结果天然不重，不必最后再去一遍重。回溯的通用框架见 DFS 深度优先搜索。

数据规模与复杂度¶

数据范围写 n < 10，输入描述说「长度不超过 10，字符只包括大小写字母」，按较宽的一边估：无重复时结果最多 10! = 3628800 个串，每个还要 join 出长度 10 的字符，量级 3.6e7 字符——这已经是这类题的上限，时限「其他语言 2 秒」刚好吃得下。时间 O(n * n!)、空间 O(n * n!)，主要都花在结果集本身；剪枝去重不只是为了正确，也直接砍掉重复分支的时间。

坑在哪¶

必须先排序。同层剪枝的前提是「相同字符相邻」，不排序时重复字符散落各处， i-1 位置上不一定是同一个字符，剪枝条件形同虚设。
剪枝条件判的是 not used[i-1]：前一个相同字符尚未被使用，说明本层刚试过它、并已回溯撤销，再选当前这个得到的是同一批排列。整条剪枝去掉的话，"aab" 会输出 6 个串、其中 3 个是重复项，与期望的 3 个对不上。
这题是多解的：meta.json 的 judge 给 BM58 配了 unordered（按集合比对），因为题面写明「可以以任意顺序返回这个字符串数组」，示例 1 的说明也讲返回 ["ba","ab"] 同样正确。但「顺序任意」只放宽了排列之间的先后，不放宽内容：多吐一个重复串照样判错。
参数名 str 来自官方模板，不能改，它在函数体内遮蔽了内置的 str—— 这个函数里不能再调用 str(...) 做类型转换，会当成对字符串参数取调用而 TypeError。
三步「做选择、递归、撤销选择」必须成对：path.pop() 与 used[i] = False 漏一个，状态就会串到兄弟分支上，结果既缺又乱。
空串是合法输入，此时 n = 0，递归立刻命中终止条件，返回 [""] 而不是空列表。

样例复核¶

"aab" 排序后仍是 a a b。第一位取下标 0 的 a，剩下 a、b 展开出 "aab"、"aba"；第一位取下标 1 的 a 被同层剪枝挡掉；第一位取 b，展开出 "baa"。共 3 个串，正是 3!/2! 的去重结果。

参考实现¶

solutions/nowcoder/BM58/sol.py
from typing import List, Optional


class Solution:
    def Permutation(self, str: str) -> List[str]:
        chars = sorted(str)             # 排序：让相同字符相邻，才能用「同层跳过」去重
        n = len(chars)
        # used[i] 标记下标 i 是否已填进 path，回溯时必须原样撤销
        used = [False] * n
        path: List[str] = []
        res: List[str] = []

        def backtrack() -> None:
            # 填满 n 位即得到一个排列，收下后回退，换本层的下一个选择
            if len(path) == n:
                res.append("".join(path))
                return
            # 本层枚举「这一位填哪个下标」，同一层里每种字符只允许被选一次
            for i in range(n):
                if used[i]:
                    continue
                # 同层去重：与前一个字符相同、且前一个刚被撤销，说明这个分支已经走过
                if i > 0 and chars[i] == chars[i - 1] and not used[i - 1]:
                    continue
                # 做选择 -> 递归 -> 撤销选择，三步成对，状态才不会串到兄弟分支
                used[i] = True
                path.append(chars[i])
                backtrack()
                path.pop()
                used[i] = False

        backtrack()
        return res

BM58 字符串的排列¶