class Solution {
public:
string customSortString(string order, string s) {
}
};
791. 自定义字符串排序
给定两个字符串 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 <= s.length <= 200order 和 s 由小写英文字母组成order 中的所有字符都 不同原站题解
golang 解法, 执行用时: 0 ms, 内存消耗: 1.8 MB, 提交时间: 2022-11-13 11:07:50
func customSortString(order string, s string) string {
d := [26]int{}
for i := range order {
d[order[i]-'a'] = i
}
cs := []byte(s)
sort.Slice(cs, func(i, j int) bool { return d[cs[i]-'a'] < d[cs[j]-'a'] })
return string(cs)
}
golang 解法, 执行用时: 0 ms, 内存消耗: 1.9 MB, 提交时间: 2022-11-13 11:07:33
func customSortString(order string, s string) string {
cnt := [26]int{}
for _, c := range s {
cnt[c-'a']++
}
ans := []rune{}
for _, c := range order {
for cnt[c-'a'] > 0 {
ans = append(ans, c)
cnt[c-'a']--
}
}
for i, v := range cnt {
for j := 0; j < v; j++ {
ans = append(ans, rune('a'+i))
}
}
return string(ans)
}
python3 解法, 执行用时: 32 ms, 内存消耗: 15.1 MB, 提交时间: 2022-11-13 11:07:15
class Solution:
def customSortString(self, order: str, s: str) -> str:
'''
计数排序
'''
freq = Counter(s)
ans = list()
for ch in order:
if ch in freq:
ans.extend([ch] * freq[ch])
freq[ch] = 0
for (ch, k) in freq.items():
if k > 0:
ans.extend([ch] * k)
return "".join(ans)
python3 解法, 执行用时: 40 ms, 内存消耗: 15 MB, 提交时间: 2022-11-13 11:05:05
class Solution:
def customSortString(self, order: str, s: str) -> str:
d = {c: i for i, c in enumerate(order)}
return ''.join(sorted(s, key=lambda x: d.get(x, 0)))