自定义字符串排序

难度: Medium

给定两个字符串 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"
解释：字符 "b"、"c" 和 "a" 规定了 s 中字符的顺序。s 中的字符 "d" 没有在 order 中出现，所以它的位置是弹性的。

按照出现的顺序，s 中的 "b"、"c"、"a" 应排列为"b"、"c"、"a"。"d" 可以放在任何位置，因为它没有按顺序排列。输出 "bcad" 遵循这一规则。其他排序如 "bacd" 或 "bcda" 也是有效的，只要维持 "b"、"c"、"a" 的顺序。

提示:

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

Submission

运行时间: 20 ms

内存: 0.0 MB

class Solution:
    def customSortString(self, S: str, T: str) -> str:
        ans=""
        ct=collections.Counter(T)
        for s in S:
            if s in ct:
                ans+=(s*ct.pop(s))
        for k,v in ct.items():
            ans+=(k*v)
        return ans

Explain

题解的思路是首先使用collections.Counter统计字符串T中各字符的出现频次。然后，按照字符串S（order）给定的顺序，从计数器中取出相应字符，并构建结果字符串。这确保了S中的字符在结果中的顺序是正确的。如果T中有字符不在S中，这些字符将保留在Counter中。最后，将剩余的字符按其原有频次添加到结果字符串的末尾。这样，S中未提及的字符将按T中的出现顺序排列。

时间复杂度: O(n)

空间复杂度: O(1)

import collections

class Solution:
    def customSortString(self, S: str, T: str) -> str:
        ans = ''
        # 使用Counter统计字符串T中字符的频次
        ct = collections.Counter(T)
        # 遍历S中的字符，按顺序添加到结果字符串中
        for s in S:
            if s in ct:
                ans += (s * ct.pop(s))
        # 添加剩余的字符，这些字符在S中没有出现
        for k, v in ct.items():
            ans += (k * v)
        return ans

Explore

`collections.Counter`是Python中用于计数的专门数据结构，它能够以字典形式存储元素及其计数，让频次统计变得更加直接和高效。使用Counter可以简化代码，并自动处理频次的累加，比手动维护字典或数组更为方便。此外，Counter提供了许多便利的方法，如`most_common`和`pop`，可以在算法实现中提供额外的帮助。

算法通过在最终添加剩余字符的步骤中维持`collections.Counter`中的顺序来实现。在Python中，`collections.Counter`遍历时是按照元素首次添加的顺序进行的。因此，对于T中存在但不在S中的字符，在将它们添加到最终结果字符串时，会按照它们在字符串T中出现的顺序来添加，从而保持了相对顺序的一致性。

使用`ct.pop(s)`的主要优势是在取出元素的同时将其从计数器中移除，这样做可以避免对已经处理过的字符进行重复处理。这不仅清理了数据结构，还减少了后续操作的复杂性，因为我们不需要额外的逻辑来跳过已经添加到结果字符串中的字符。这样的操作使得代码更简洁，逻辑更清晰。

如果`order`中的字符在`s`中不出现，这不会影响到最终结果字符串的正确性，但会增加一些无效的操作。在算法中，会遍历`order`中的每个字符并尝试从计数器中移除并添加到结果字符串。如果这些字符在`s`中不存在，那么相应的频次为零，这部分操作实际上是不会对结果字符串产生任何添加。因此，这种情况只是影响了算法的效率，而不影响结果的正确性。