LeetCode 791. 自定义字符串排序

Categories:

题目描述
思路分析
1. 解法一：计数重排（推荐）
相似题目

题目描述

✅ 791. 自定义字符串排序

思路分析

解法一：计数重排（推荐）

核心思路：

统计 s 中每个字符的出现次数。

按 order 的顺序输出对应字符，次数用尽后输出剩余字符。

全程只需 26 个计数桶。

复杂度分析：

时间复杂度：O(n)，其中 n 表示字符串长度。

空间复杂度：O(1)，仅使用固定大小计数数组。

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)
}

相似题目

题目	难度	考察点
242. 有效的字母异位词	简单	计数
451. 根据字符出现频率排序	中等	计数
692. 前K个高频单词	中等	堆
438. 找到字符串中所有字母异位词	中等	滑动窗口
567. 字符串的排列	中等	滑动窗口

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2024/91603497