C++ 中的自定义排序字符串
c++server side programmingprogramming更新于 2024/11/8 21:59:00
假设我们有 S 和 T 两个字符串，它们由小写字母组成。在 S 中，没有字母出现超过一次。S 之前按某种自定义顺序排序。我们必须对 T 的字符进行排列，以便它们与 S 的排序顺序相匹配。更具体地说，如果 x 在 S 中出现在 y 之前，那么在返回的字符串中 x 将出现在 y 之前。
因此，如果 S = "cba" 且 T = "abcd"，则输出将为 "cbad"。这里 S 中出现了 "a"、"b"、"c"，因此 "a"、"b"、"c" 的顺序应该是 "c"、"b" 和 "a"。由于"d"未出现在S中，因此它可以位于T中的任何位置。"dcba"、"cdba"、"cbda"也是有效输出。
为了解决这个问题，我们将遵循以下步骤−
将ret设置为空字符串
定义一个映射m，并将T中存在的每个字符的频率存储到m中
对于i，范围为0到S的大小– 1
x := S[i]
对于j，范围为0到m[x] – 1
ret := ret + x
m[x] := 0
对于 m 中的每一对，it −
如果 it 的值 > 0，则
对于 i，范围从 0 到 it 的值 – 1
ret := ret 连接它的键
return ret
Example(C++)
让我们看下面的实现，以便更好地理解 −
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
string customSortString(string S, string T) {
string ret = "";
unordered_map <char, int> m;
for(int i = 0; i < T.size(); i++){
m[T[i]]++;
}
for(int i = 0; i < S.size(); i++){
char x = S[i];
for(int j = 0; j < m[x]; j++){
ret += x;
}
m[x] = 0;
}
unordered_map <char, int> :: iterator it = m.begin();
while(it != m.end()){
if(it->second > 0){
for(int i = 0; i < it->second; i++)ret += it->first;
}
it++;
}
return ret;
}
};
main(){
Solution ob;
cout << (ob.customSortString("cba", "abcd"));
}
输入
"cba" "abcd"
输出
cbad
