LeetCode 791. 自定义字符串排序

2024-10-28 HGNULB 约 9 分钟

文章信息 9 个分类 3 个标签

分类

题目描述

✅ 791. 自定义字符串排序

题意分析

给两个只含小写字母的字符串 order 和 s，其中 order 内部字符互不重复。要求重排 s，使得凡是同时出现在 order 里的两个字符 x、y，若 x 在 order 中排在 y 前面，则重排后 s 中所有的 x 都必须排在所有的 y 前面。不在 order 中的字符可以放在任意位置。答案不唯一，返回任何一个合法结果即可。

约束里有两条关键信号。第一，字符集固定为 26 个小写字母，这意味着任何「按字符归类」的操作都可以用一个定长数组完成，不需要哈希表也不需要动态扩容。第二，题目只约束相对顺序，完全不关心某个字符原来在 s 的第几位——同一个字母的多个副本彼此不可区分，交换它们不影响结果。这就等于宣布：s 的位置信息是冗余的，只有「每个字母出现了几次」这 26 个数字是有用的。

一旦承认位置信息可丢，输出就不是「排序」而是「按某个顺序把桶里的字母倒出来」。这是本题真正的解法入口。

边界有三处：s 里可能含有 order 中不存在的字符，它们必须一个不漏地出现在答案里，只是位置自由；order 里可能含有 s 中不存在的字符，这些字符不该凭空出现在答案里；两个串长度都可能为 1。此外答案长度必须严格等于 s 的长度，多一个或少一个都是错的。

解法：计数重排

核心思路

先看最直接的写法：把 s 拆成字符数组，用一个比较器排序，比较键取该字符在 order 中的下标，不在 order 中的统一取一个比所有下标都大的值（比如 26）。这个做法是对的，但要付出 $O(n \log n)$ 的比较代价，而且每次比较都要在 order 里查一次下标。

瓶颈在于：排序算法假设元素两两不同、需要逐对比较才能定序。但这里的比较键只有 26 种取值，而取值相同的元素本身也完全相同——键为 3 的字符必然都是同一个字母。既然如此，排序做的所有比较工作都是在重复确认一件早就知道的事。

由此得到观察：只要知道每个字母出现了多少次，答案就可以直接「按顺序印出来」，一次比较都不用做。order 给出了前一部分的印刷顺序，剩下的字母随便什么顺序印都合法。

于是维护一个长度 26 的计数数组 cnt，全程的不变量是：cnt[c] 恒等于字符 c 中「还没有被写进结果」的个数。初始化时 cnt 装的是 s 的全部字符，此时结果为空；每往结果里追加一个 c 就把 cnt[c] 减一。因此任意时刻都有 已写入长度 + cnt 各项之和 = s.length，当所有 cnt 归零时结果长度自然等于 s.length，不多也不少。

输出分两趟：第一趟按 order 的顺序把命中的字母全部倒空，第二趟扫 26 个桶把剩下的倒空。第一趟保证了 order 约束成立——先倒的字母整体排在后倒的字母之前；第二趟处理的字符不受任何约束，放在末尾必然合法。这里也解释了为什么 order 中 s 没有的字符不会带来麻烦：它的计数本来就是 0，while 循环一次都不进。

解题步骤

建立计数：遍历 s，cnt[ch - 'a']++。用 ch - 'a' 把字符映射成 0..25 的下标，这是小写字母题的标准手法，比哈希表省掉装箱和哈希计算。

准备可变的结果容器：Java 用 StringBuilder，Go 用预分配 len(s) 容量的 []byte。不能用字符串拼接，那样每次追加都会复制整个前缀，总代价退化成 $O(n^2)$。

第一趟按 order 输出：对 order 的每个字符 ch，只要 cnt[ch - 'a'] > 0 就追加一个 ch 并把计数减一。用 while 而不是 if，因为同一个字母在 s 中可能出现多次，必须一次性全部倒空——否则它的副本会漏到第二趟去，破坏相对顺序。

计数清零即是标记：减到 0 这个动作同时完成了「已输出」的标记，第二趟看到 0 自然跳过。不需要额外的 visited 数组，这是让计数数组一身二职的小技巧。

第二趟输出剩余：从 0 到 25 扫一遍，把还有余量的字母全部追加。这些字符不在 order 里（在 order 里的已经被清零了），顺序任意，这里恰好是字典序。

返回结果：把容器转成字符串。

以 order = "cba"、s = "abcd" 走一遍。

建表后：cnt['a'] = 1、cnt['b'] = 1、cnt['c'] = 1、cnt['d'] = 1，其余全 0，结果串为空。
第一趟第 1 轮：ch = 'c'，cnt['c'] = 1 > 0，追加得 "c"，cnt['c'] 降为 0；再判一次已是 0，退出内层循环。
第一趟第 2 轮：ch = 'b'，追加得 "cb"，cnt['b'] 降为 0。
第一趟第 3 轮：ch = 'a'，追加得 "cba"，cnt['a'] 降为 0。
此时 cnt 中只剩 cnt['d'] = 1。
第二趟：下标 0..2 对应的 a、b、c 计数都是 0，跳过；下标 3 对应 d，计数为 1，追加得 "cbad"，减为 0；其余下标全 0。
返回 "cbad"，长度 4 与 s 相同，c 在 b 前、b 在 a 前，符合 order；d 不受约束。

再看一个含重复字符的例子体会 while 的必要性：order = "cba"、s = "aabbcc" 时，第一趟每个字母都要连倒两次，得到 "ccbbaa"。如果内层写成 if，只会各倒一个得到 "cba"，剩下的 a、b、c 被第二趟以字典序追加成 "cbaabc"——里面 a 跑到了 b、c 前面，直接违反 order。

代码实现

class Solution {
    // 按 order 的顺序输出对应字符，次数用尽后输出剩余字符。
    public String customSortString(String order, String s) {
        int[] cnt = new int[26];
        for (char ch : s.toCharArray()) {
            cnt[ch - 'a']++;
        }

        StringBuilder sb = new StringBuilder();
        for (char ch : order.toCharArray()) {
            while (cnt[ch - 'a'] > 0) {
                sb.append(ch);
                cnt[ch - 'a']--;
            }
        }

        for (int i = 0; i < 26; i++) {
            while (cnt[i] > 0) {
                sb.append((char) ('a' + i));
                cnt[i]--;
            }
        }

        return sb.toString();
    }
}

func customSortString(order string, s string) string {
    // 按 order 的顺序输出对应字符，次数用尽后输出剩余字符。
    cnt := make([]int, 26)
    for i := 0; i < len(s); i++ {
        cnt[s[i]-'a']++
    }

    res := make([]byte, 0, len(s))
    for i := 0; i < len(order); i++ {
        ch := order[i]
        for cnt[ch-'a'] > 0 {
            res = append(res, ch)
            cnt[ch-'a']--
        }
    }

    for i := 0; i < 26; i++ {
        for cnt[i] > 0 {
            res = append(res, byte('a'+i))
            cnt[i]--
        }
    }

    return string(res)
}

复杂度分析

时间复杂度：$O(n + m)$，其中 $n$ 为 s 长度、$m$ 为 order 长度。建表扫一遍 s；两趟输出的内层 while 总执行次数等于 s 的长度（每次执行必定写出一个字符且计数减一，总减少量恰好是 $n$），外层是 $m + 26$ 次判断。全程没有任何比较排序，凭的就是「比较键只有 26 种且键相同即元素相同」这一点。

空间复杂度：$O(1)$ 额外空间，计数数组固定 26 个整数，与输入规模无关；返回的结果串占 $O(n)$，但那是必需的输出而非辅助结构。

关键点总结

当排序键的值域是小常数、且键相同的元素彼此不可区分时，比较排序可以整体降级为计数排序，$O(n \log n)$ 直接降到 $O(n)$。这是本题最值得迁移的一条。

题目只约束相对顺序而不约束绝对位置，是「可以丢掉原始下标」的许可证。看到这句话就该想到计数。

让计数数组一身二职：数值既是剩余个数，归零又充当「已处理」标记，省掉一个 visited 数组。

分两趟输出的正确性证明很短——第一趟内部满足 order，第二趟的字符不受任何约束，因此整体合法。面试时把这两句说出来，比默写代码有说服力得多。

面试视角：面试官通常会先接受 $O(n \log m)$ 的自定义比较器解法，然后追问「能不能做到线性」。如果你能主动指出比较键只有 26 种取值、进而给出计数版本，并顺带说明 StringBuilder 与字符串拼接的复杂度差别，这道题就答满了。

追问的常见延伸是「如果字符集是全 Unicode 呢」：此时计数数组换成哈希表，第二趟改为遍历哈希表的键，复杂度变成 $O(n + m)$ 期望，结论不变。

易错点总结

内层用 if 而非 while：order = "cba"、s = "aabbcc" 时第一趟只输出 "cba"，剩余的 a 被第二趟按字典序放到最前，得到 "cbaabc"，a 出现在 c 之前，判定失败。

输出后忘记把计数清零：order = "cba"、s = "abc" 时 c、b、a 在第二趟被再次输出，返回 "cbaabc"，长度 6 而 s 长度只有 3。

只输出 order 中的字符，漏掉第二趟：order = "cba"、s = "abcd" 返回 "cba"，字符 d 凭空消失。

第二趟遍历 s 而不是 26 个桶：s = "aabbcc" 时同一个字母会被它的每个副本各触发一次判断，若同时忘了清零就会重复输出；即便写对了也白白多出 $O(n)$ 次无效判断，并且逻辑上更容易和第一趟的清零耦合出错。

用字符串拼接代替 StringBuilder：s 长度为 200 时看不出问题，但写法本身是 $O(n^2)$，面试官几乎必问，属于送分变送命。

假设 order 一定包含 s 的所有字符：order = "kqep"、s = "pekeq" 尚可，但 order = "kqep"、s = "pekexlz" 中的 x、l、z 会被吞掉。题目从未保证 order 是全集。

假设 s 一定包含 order 的所有字符：若第一趟不判断 cnt > 0 就无脑追加一次，order = "abc"、s = "b" 会返回 "abc"，凭空造出两个不存在的字符，并把计数减成负数。

用 ch - 'A' 或直接拿 ch 当下标：前者对小写字母算出负下标直接数组越界，后者需要长度 128 的数组，用 26 会 ArrayIndexOutOfBoundsException。

Go 里对字符串用 range 取字符：for i, ch := range s 拿到的 ch 是 rune 且 i 是字节偏移，虽然本题全是 ASCII 不会出错，但与 res = append(res, ch) 的 byte 类型不匹配，编译期就会报错。

相似题目

题目	难度	考察点
1122. 数组的相对排序	简单	同款「按给定序列重排」，但值域是 0..1000 的整数，且未命中的部分要求升序而非任意序
451. 根据字符出现频率排序	中等	排序键改成出现次数而非外部给定顺序，需要对计数结果再排序或用桶排序
75. 颜色分类	中等	同样是常数值域，但要求原地且一趟完成，只能用三指针而不能用计数两趟
49. 字母异位词分组	中等	计数结果不用来输出，而是当作分组的哈希键
242. 有效的字母异位词	简单	只需比较两张计数表是否相等，不涉及任何输出顺序
387. 字符串中的第一个唯一字符	简单	计数后必须回到原串按下标扫描，位置信息在这里恰恰不能丢
347. 前 K 个高频元素	中等	值域无界，计数之后靠堆或桶排序取前 K，而非全量重排