LeetCode 791. 自定义字符串排序
题目描述
题意分析
order中的字符互不相同，它们规定了一部分字母的先后顺序。需要重新排列字符串s的全部字符，使在order中更靠前的字符，其所有出现都排在后面的受约束字符之前，返回任意一种符合规则的排列。不在
order里的字符没有位置限制，但仍必须完整保留。输出只是原字符的重排，不能增加、删除或合并重复字符。两个输入都只含小写英文字母，因此字符范围固定为二十六种。
解法：计数重排
核心思路
[!blue]
同一种字符的各个副本没有区别，原来的出现位置也不需要保留，所以先统计
s中二十六个字母各有多少份。知道每个字母的数量，就能直接按指定次序构造结果，无需进行逐字符比较排序。依次遍历
order中的字母，每次把当前字母剩余的所有份数写入结果，并把计数逐个减到零。这样一个优先级的字符会完整输出后才处理下一个优先级，所有受约束字母自然满足指定顺序；如果该字母在s中不存在，计数为零，直接跳过。第一轮结束后，非零计数只可能属于没有出现在
order中的字母。再遍历整张频次数组，把这些剩余字符补到结果末尾即可。它们之间没有指定顺序，按普通字母顺序追加只是其中一种合法选择；已处理字母的计数为零，不会被重复输出。每次写入都消耗一份实际计数，最后所有计数归零，因此输出数量与输入完全一致，既满足顺序，也不会丢字符或凭空生成字符。
解题步骤
- 创建长度为二十六的计数数组，统计
s的所有字符。- 按
order顺序处理每个字母，反复追加它并减少计数，直到该字母计数为零。- 扫描全部二十六个位置，将剩余计数对应的字符逐个追加到结果。
- 返回构造好的字符串。
代码实现
class Solution {
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 {
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 + 26)$，
n为s长度，m为order长度。虽然有内层重复追加，但每份字符总共只输出一次。- 空间复杂度：$O(n + m)$ 上界，包含结果缓冲和 Java 实现生成的字符数组；频次数组本身为固定大小。
关键点总结
[!green]
- 频次代替原始位置，直接按优先级输出整组同字符副本。
- 输出时同步消耗计数，第一轮与补余量阶段不会重复生成字符。
- 未指定顺序的字符可以放在末尾，但数量不能省略。
易错点总结
[!yellow]
- 每个字母只输出一次，会丢掉输入里的重复副本。
- 把
order中所有字符都输出，即使它没有出现在s，会凭空增加字符。- 第一轮处理后不清空计数，补余量时会再次输出同一个字母。
- 只处理
order而不补剩余字符，会删除所有不受顺序约束的内容。- 把未出现在
order中的字符顺序也认定为唯一，误解了允许返回任意合法排列的要求。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 1122. 数组的相对排序 | 简单 | 规则相同地由外部序列规定部分值优先级，本题对象是字符，原题对象是整数。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！