自定义字符串排序 图解题解

这道题到底在问什么

输入

order="cba", s="abcd"

输出

"cbad" （c、b、a 在前，d 在后）

输入

order="bcafg", s="abcd"

输出

"bcad" （d 不在 order 中，放末尾）

最优解：一步一步想明白

1. 3记住「先数次数，再按 order 成串输出，最后补 order 外字符」，下面每帧都在套它。
2. 4第一段:从左到右扫 s，每遇到一个字符，就在「字符 → 出现次数」表里给它加一。
3. 5扫到第 0 个，是字符 'a'（绿色是它之前出现过的位置）。给它的出现次数加一。
4. 6字符 'a' 的出现次数更新到 1（高亮行）。继续往后扫。
5. 7扫到第 1 个，是字符 'b'（绿色是它之前出现过的位置）。给它的出现次数加一。
6. 8字符 'b' 的出现次数更新到 1（高亮行）。继续往后扫。
7. 9扫到第 2 个，是字符 'a'（绿色是它之前出现过的位置）。给它的出现次数加一。
8. 10字符 'a' 的出现次数更新到 2（高亮行）。继续往后扫。
9. 11扫到第 3 个，是字符 'c'（绿色是它之前出现过的位置）。给它的出现次数加一。
10. 12字符 'c' 的出现次数更新到 1（高亮行）。继续往后扫。
11. 13扫到第 4 个，是字符 'b'（绿色是它之前出现过的位置）。给它的出现次数加一。
12. 14字符 'b' 的出现次数更新到 2（高亮行）。继续往后扫。
13. 15扫到第 5 个，是字符 'd'（绿色是它之前出现过的位置）。给它的出现次数加一。
14. 16字符 'd' 的出现次数更新到 1（高亮行）。继续往后扫。
15. 17第一段扫完。各字符出现次数是 'a'→2，'b'→2，'c'→1，'d'→1。接下来第二段:按 order="cab" 的顺序把字符成串输出。
16. 18第二段:沿着 order="cab" 从左到右走。每个字符在表里有几个，就连续输出几个，然后把它的次数清零。
17. 19order 走到 'c'，计数表里有 1 个 'c'（绿色是它在 s 中的位置）。一次性输出 1 个 'c'，输出串变成 "c"。
18. 20把 'c' 的次数清零（高亮行已归 0，灰色表示这些位置已消化）。order 里没有重复字符，'c' 不会再被处理。
19. 21order 走到 'a'，计数表里有 2 个 'a'（绿色是它在 s 中的位置）。一次性输出 2 个 'a'，输出串变成 "caa"。
20. 22把 'a' 的次数清零（高亮行已归 0，灰色表示这些位置已消化）。order 里没有重复字符，'a' 不会再被处理。
21. 23order 走到 'b'，计数表里有 2 个 'b'（绿色是它在 s 中的位置）。一次性输出 2 个 'b'，输出串变成 "caabb"。
22. 24把 'b' 的次数清零（高亮行已归 0，灰色表示这些位置已消化）。order 里没有重复字符，'b' 不会再被处理。
23. 25order="cab" 全部走完，输出串是 "caabb"。但表里 'd' 的次数还没清零，因为它不在 order 里。第三步:再扫一遍 s，把这些剩下的字符补到末尾。
24. 26扫到 s[5]='d'，它不在 order 里、表里还剩 1 个（红色是它的位置）。直接把 1 个 'd' 补到输出串末尾 → "caabbd"，再清零。
25. 27表里所有次数都清零了，说明 s 的每个字符都进了输出串。最终重排结果 = "caabbd"。order 里的 'c'、'a'、'b' 按优先级在前，'d' 在最后。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

class Solution:
    def customSortString(self, order: str, s: str) -> str:
        cnt = {ch: 0 for ch in set(s)}
        for ch in s:
            cnt[ch] = cnt.get(ch, 0) + 1
        ans = []
        for ch in order:
            ans.append(ch * cnt.get(ch, 0))
            cnt[ch] = 0
        for ch in s:
            if cnt.get(ch, 0):
                ans.append(ch * cnt[ch])
                cnt[ch] = 0
        return ''.join(ans)

#include <string>
#include <vector>
using namespace std;
class Solution {
public:
    string customSortString(string order, string s) {
        vector<int> cnt(26);
        for (char c : s) cnt[c - 'a']++;
        string ans;
        for (char c : order) {
            ans.append(cnt[c - 'a'], c);
            cnt[c - 'a'] = 0;
        }
        for (char c : s) if (cnt[c - 'a']) {
            ans.append(cnt[c - 'a'], c);
            cnt[c - 'a'] = 0;
        }
        return ans;
    }
};

import java.util.*;
class Solution {
    public String customSortString(String order, String s) {
        int[] cnt = new int[26];
        for (char c : s.toCharArray()) cnt[c - 'a']++;
        StringBuilder ans = new StringBuilder();
        for (char c : order.toCharArray()) {
            while (cnt[c - 'a']-- > 0) ans.append(c);
        }
        for (char c : s.toCharArray()) {
            while (cnt[c - 'a']-- > 0) ans.append(c);
        }
        return ans.toString();
    }
}

复杂度

面试官可能追问