LeetCode 0791. 自定义字符串排序

【LetMeFly】791.自定义字符串排序

力扣题目链接：https://leetcode.cn/problems/custom-sort-string/

给定两个字符串 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 <= 26
• 1 <= s.length <= 200
• order 和 s 由小写英文字母组成
• order 中的所有字符都 不同

方法一：自定义排序规则

$order$中未出现过的元素不需考虑，只需要给出现过的元素编个号。

使用数组$char2th[26]$来记录26个字母的出现顺序

对于$order$中出现过的字母，我们更新其出现位置$char2th$；对于$order$中未出现过的字母，我们无需考虑其在$char2th$中的值

在排序的时候，我们以字母在$char2th$中的大小为原则进行排序即可。

• 时间复杂度$O(L1+L2\log L2)$，其中$L1=len(order),L2=len(s)$
• 空间复杂度$O(C+\log L2)$

AC代码

C++

int char2th[26];

bool cmp(const char& a, const char& b) {
    return char2th[a - 'a'] < char2th[b - 'a'];
}

class Solution {
private:
    void init(string& order) {
        for (int i = order.size() - 1; i >= 0; i--)
            char2th[order[i] - 'a'] = i;
    }
public:
    string customSortString(string& order, string& s) {
        init(order);
        sort(s.begin(), s.end(), cmp);
        return s;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

同步发文于CSDN，原创不易，转载请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/127829276