【自定义字符串排序】

来源：力扣（LeetCode）

描述：

给定两个字符串 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”也是有效的输出。
1
2
3
4
5

示例 2:

输入: order = "cbafg", s = "abcd"
输出: "cbad"
1
2

提示:

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

方法一：自定义排序

思路与算法

最简单的方法是直接对字符串 s 进行排序。

我们首先遍历给定的字符串 order，将第一个出现的字符的权值赋值为 1，第二个出现的字符的权值赋值为 2，以此类推。在遍历完成之后，所有未出现字符的权值默认赋值为 0。

随后我们根据权值表，对字符串 s 进行排序，即可得到一种满足要求的排列方案。

代码：

class Solution {
public:
    string customSortString(string order, string s) {
        vector<int> val(26);
        for (int i = 0; i < order.size(); ++i) {
            val[order[i] - 'a'] = i + 1;
        }
        sort(s.begin(), s.end(), [&](char c0, char c1) {
            return val[c0 - 'a'] < val[c1 - 'a'];
        });
        return s;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

复杂度分析
时间复杂度：O(nlog⁡n + ∣Σ∣)，其中 n 是字符串 s 的长度，Σ 是字符集，在本题中 ∣Σ∣ = 26。排序的时间复杂度为 O(nlog⁡n)；如果我们使用数组存储权值，数组的大小为 O(∣Σ∣)；如果我们使用哈希表存储权值，哈希表的大小与字符串 sss 和 order 中出现的字符种类数相同，为叙述方便也可以记为 O(∣Σ∣)。
空间复杂度：O(∣Σ∣)。即为数组或哈希表需要使用的空间。

方法二：计数排序

思路与算法

由于字符集的大小为 26，我们也可以考虑使用计数排序代替普通的排序方法。

我们首先遍历字符串 s，使用数组或哈希表统计每个字符出现的次数。随后遍历字符串 order 中的每个字符 c，如果其在 s 中出现了 k 次，就在答案的末尾添加 k 个 c，并将数组或哈希表中对应的次数置为 0。最后我们遍历一次哈希表，对于所有次数 k 非 0 的键值对 (c,k)，在答案的末尾添加 k 个 c 即可。

代码:

class Solution {
public:
    string customSortString(string order, string s) {
        vector<int> freq(26);
        for (char ch: s) {
            ++freq[ch - 'a'];
        }
        string ans;
        for (char ch: order) {
            if (freq[ch - 'a'] > 0) {
                ans += string(freq[ch - 'a'], ch);
                freq[ch - 'a'] = 0;
            }
        }
        for (int i = 0; i < 26; ++i) {
            if (freq[i] > 0) {
                ans += string(freq[i], i + 'a');
            }
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

复杂度分析
时间复杂度：O(n+∣Σ∣)，其中 n 是字符串 s 的长度，Σ 是字符集，在本题中 ∣Σ∣ = 26。
空间复杂度：O(∣Σ∣)。即为数组或哈希表需要使用的空间。
author：力扣官方题解