C ++中的自定义排序字符串

假设我们有S和T两个字符串，它们由小写字母组成。在S中，没有字母出现多次。S以前以某些自定义顺序排序。我们必须置换T的字符，以便它们与S的排序顺序匹配。更具体地说，如果x在S中的y之前出现，则x在返回的字符串中的y之前出现。

因此，如果S =“ cba”和T =“ abcd”，则输出将为“ cbad”。这里的“ a”，“ b”，“ c”出现在S中，因此“ a”，“ b”，“ c”的顺序应为“ c”，“ b”和“ a”。由于“ d”未出现在S中，因此它可以在T中的任何位置。“ dcba”，“ cdba”，“ cbda”也是有效的输出。

为了解决这个问题，我们将遵循以下步骤-

• 将ret设置为空字符串

• 定义一个映射m，并将T中存在的每个字符的频率存储到m中

• 对于范围从0到S – 1的i

• ret：= ret + x

• x：= S [i]

• 对于j，范围从0到m [x] – 1

• m [x]：= 0

• 对于每对，它在m-

• 因为我的范围是0到它的值– 1

• ret：= ret连接它的键

• 如果它的值> 0，则

• 返回ret

例子（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