791. 自定义字符串排序 : 简单构造题

冷不防 2023-10-03 21:28 22阅读 0赞

![format_png][]

### 题目描述 ###

这是 LeetCode 上的 **[791. 自定义字符串排序][791.]** ，难度为 **中等**。

Tag : 「构造」、「模拟」

给定两个字符串 `order` 和 `s` 。`order` 的所有单词都是 唯一 的，并且以前按照一些自定义的顺序排序。

对 `s` 的字符进行置换，使其与排序的 `order` 相匹配。更具体地说，如果在 `order` 中的字符 `x` 出现字符 `y` 之前，那么在排列后的字符串中， `x` 也应该出现在 `y` 之前。

返回 满足这个性质的 `s` 的任意排列 。

示例 1:

输入: order = "cba", s = "abcd"
    
    输出: "cbad"
    
    解释: 
    “a”、“b”、“c”是按顺序出现的，所以“a”、“b”、“c”的顺序应该是“c”、“b”、“a”。
    因为“d”不是按顺序出现的，所以它可以在返回的字符串中的任何位置。“dcba”、“cdba”、“cbda”也是有效的输出。
    复制代码

示例 2:

输入: order = "cbafg", s = "abcd"
    
    输出: "cbad"
    复制代码

提示:

*  1 <= order.length <= 261<=order.length<=26
 *  1 <= s.length <= 2001<=s.length<=200
 *  `order` 和 `s` 由小写英文字母组成
 *  `order` 中的所有字符都 不同

### 构造 ###

根据题意进行模拟即可：起始先使用大小为 C = 26C=26 的数组 `cnts` 对 `s` 的所有字符进行词频统计，随后根据 `order` 的优先级进行构造。

若字符 `x` 在 `order` 中排于 `y` 前面，则先往答案追加 `cnts[x]` 个字符 `x`，再往答案追加 `cnts[y]` 个字符 `y`，并更新对应词频，最后将仅出现在 `s` 中的字符追加到答案尾部。

Java 代码：

class Solution {
        public String customSortString(String order, String s) {
            int[] cnts = new int[26];
            for (char c : s.toCharArray()) cnts[c - 'a']++;
            StringBuilder sb = new StringBuilder();
            for (char c : order.toCharArray()) {
                while (cnts[c - 'a']-- > 0) sb.append(c);
            }
            for (int i = 0; i < 26; i++) {
                while (cnts[i]-- > 0) sb.append((char)(i + 'a'));
            }
            return sb.toString();
        }
    }
    复制代码

TypeScript 代码：

Python 代码：

class Solution:
        def customSortString(self, order: str, s: str) -> str:
            cnts = [0] * 26
            for c in s:
                cnts[ord(c) - ord('a')] += 1
            ans = ''
            for c in order:
                num = ord(c) - ord('a')
                if cnts[num] > 0:
                    ans += c * cnts[num]
                    cnts[num] = 0
            for i in range(26):
                if cnts[i] > 0:
                    ans += chr(i + ord('a')) * cnts[i]
            return ans
    复制代码

*  时间复杂度：O(n + m)O(n+m)
 *  空间复杂度：O(C)O(C)，其中 C = 26C=26 为字符集大小

### 最后 ###

这是我们「刷穿 LeetCode」系列文章的第 `No.791` 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

[format_png]: https://img-blog.csdnimg.cn/img_convert/482d836c14d5a90a91c42d37ab28663a.webp?x-oss-process=image/format,png
[791.]: https://link.juejin.cn/?target=https%3A%2F%2Fleetcode.cn%2Fproblems%2Fcustom-sort-string%2Fsolution%2Fby-ac_oier-ali0%2F