原文链接: https://leetcode-cn.com/problems/custom-sort-string

英文原文

You are given two strings order and s. All the words of order are unique and were sorted in some custom order previously.

Permute the characters of s so that they match the order that order was sorted. More specifically, if a character x occurs before a character y in order, then x should occur before y in the permuted string.

Return any permutation of s that satisfies this property.

 

Example 1:

Input: order = "cba", s = "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.

Example 2:

Input: order = "cbafg", s = "abcd"
Output: "cbad"

 

Constraints:

• 1 <= order.length <= 26
• 1 <= s.length <= 200
• order and s consist of lowercase English letters.
• All the characters of order are unique.

中文题目

字符串S和 T 只包含小写字符。在S中，所有字符只会出现一次。

S 已经根据某种规则进行了排序。我们要根据S中的字符顺序对T进行排序。更具体地说，如果S中x在y之前出现，那么返回的字符串中x也应出现在y之前。

返回任意一种符合条件的字符串T。

示例:
输入:
S = "cba"
T = "abcd"
输出: "cbad"
解释: 
S中出现了字符 "a", "b", "c", 所以 "a", "b", "c" 的顺序应该是 "c", "b", "a". 
由于 "d" 没有在S中出现, 它可以放在T的任意位置. "dcba", "cdba", "cbda" 都是合法的输出。

注意:

• S的最大长度为26，其中没有重复的字符。
• T的最大长度为200。
• S和T只包含小写字符。

通过代码

官方题解

方法一：统计字符数量重新构造字符串【通过】

思路

首先找出在 T 中出现的所有的 S 的元素，并且将这些元素按照 S 中出现的相对顺序排序，然后把 T 中出现的但不在 S 中的元素添加到排好序的字符串中，就得到了我们想要的结果。

在将 T 中出现的但不在 S 中的元素添加到字符串时，无序关注顺序，因为这些元素并没有在 S 中出现，不需要满足排序关系。

算法

一种巧妙的实现方法是统计 T 中每个字符出现的次数，把结果存储在数组 count 中，count[char] 表示字符 char 出现的次数。然后把在 S 中出现的字符按照在 S 中的相对顺序排列，剩余字符添加到当前字符串的后面，最终排好序的字符串顺序为 S + (未在 S 中出现的字符)。

[solution1-Java]
class Solution {
    public String customSortString(String S, String T) {
        // count[char] = the number of occurrences of 'char' in T.
        // This is offset so that count[0] = occurrences of 'a', etc.
        // 'count' represents the current state of characters
        // (with multiplicity) we need to write to our answer.
        int[] count = new int[26];
        for (char c: T.toCharArray())
            count[c - 'a']++;

        // ans will be our final answer.  We use StringBuilder to join
        // the answer so that we more efficiently calculate a
        // concatenation of strings.
        StringBuilder ans = new StringBuilder();

        // Write all characters that occur in S, in the order of S.
        for (char c: S.toCharArray()) {
            for (int i = 0; i < count[c - 'a']; ++i)
                ans.append(c);
            // Setting count[char] to zero to denote that we do
            // not need to write 'char' into our answer anymore.
            count[c - 'a'] = 0;
        }

        // Write all remaining characters that don't occur in S.
        // That information is specified by 'count'.
        for (char c = 'a'; c <= 'z'; ++c)
            for (int i = 0; i < count[c - 'a']; ++i)
                ans.append(c);

        return ans.toString();
    }
}

[solution1-Python]
class Solution(object):
    def customSortString(self, S, T):
        # count[char] will be the number of occurrences of
        # 'char' in T.
        count = collections.Counter(T)
        ans = []

        # Write all characters that occur in S, in the order of S.
        for c in S:
            ans.append(c * count[c])
            # Set count[c] = 0 to denote that we do not need
            # to write 'c' to our answer anymore.
            count[c] = 0

        # Write all remaining characters that don't occur in S.
        # That information is specified by 'count'.
        for c in count:
            ans.append(c * count[c])

        return "".join(ans)

复杂度分析

• 时间复杂度：$O(S.\text{length} + T.\text{length})$，遍历 S 和 T 花费的时间。

• 空间复杂度：$O(T.\text{length})$，统计 26 个小写字母的空间和存储最终排好序的字符串 T 的空间。

统计信息

通过次数	提交次数	AC比率
12111	17384	69.7%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言