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.题目大意:
给一个字符串,求这个字符串的一个排列,使得字母顺序按照另一个给定字符串order的顺序。
解题思路:
由限制条件知道,order字母是唯一的,order字母可以重复。所以只要统计s频率,然后按照字母顺序开始重写
解题步骤:
N/A
注意事项:
Python代码:
1
2
3
4
5
6
7
8
9
10def customSortString(self, order: str, s: str) -> str:
char_to_count = collections.Counter(s)
res = ''
for c in order:
if c in char_to_count:
res += c * char_to_count[c]
char_to_count.pop(c)
for c, count in char_to_count.items():
res += c * count
return res
算法分析:
时间复杂度为O(n)
,空间复杂度O(n)