[LeetCode] 791. Custom Sort String

order and str are strings composed of lowercase letters. In order, no letter occurs more than once.

order was sorted in some custom order previously. We want to permute the characters of str so that they match the order that order was sorted. More specifically, if x occurs before y in order, then x should occur before y in the returned string.

Return any permutation of str (as a string) that satisfies this property.

Example:
Input:
order = “cba”
str = “abcd”
Output: “cbad”
Explanation:
“a”, “b”, “c” appear in order, so the order of “a”, “b”, “c” should be “c”, “b”, and “a”.
Since “d” does not appear in order, it can be at any position in the returned string. “dcba”, “cdba”, “cbda” are also valid outputs.

Note:
order has length at most 26, and no character is repeated in order.
str has length at most 200.
order and str consist of lowercase letters only.

自定义字符串排序。

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

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

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/custom-sort-string
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

思路是 counting sort 计数排序。根据题意，order 是规则，s 是需要被排序的字符串。首先我们统计一下在 order 中，每个字母分别出现了几次。统计好了之后，我们按照规则的顺序，分别检查在规则中出现的字母，是否也出现在 s 中，如果有，则将 order 中所有的字母都写入 StringBuilder。最后对于 order 中出现但是 s 中未出现的字母，我们加到 StringBuilder 的最后即可。

复杂度

时间O(n)
空间O(n)

代码

Java实现

class Solution {
    public String customSortString(String order, String s) {
        int[] map = new int[26];
        for (char c : s.toCharArray()) {
            map[c - 'a']++;
        }

        StringBuilder sb = new StringBuilder();
        int n = order.length();
        for (int i = 0; i < n; i++) {
            char c = order.charAt(i);
            while (map[c - 'a'] > 0) {
                sb.append(c);
                map[c - 'a']--;
            }
        }
        for (char c = 'a'; c <= 'z'; c++) {
            while (map[c - 'a'] > 0) {
                sb.append(c);
                map[c - 'a']--;
            }
        }
        return sb.toString();
    }
}