C++でのカスタムソート文字列

SとTの2つの文字列があり、これらは小文字で構成されているとします。 Sでは、文字が2回以上出現することはありません。 Sは、以前はカスタム順序で並べ替えられていました。 Sが並べ替えられた順序と一致するように、Tの文字を並べ替える必要があります。より具体的には、Sでxが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に格納します

• 0からS–1のサイズまでの範囲のiの場合

  • x：=S [i]

  • 0からm[x]– 1

    の範囲のjの場合

    • ret：=ret + x

  • m [x]：=0

• ペアごとにm−

  • その値が>0の場合、

    • 0からその値までの範囲のiの場合– 1

      • ret：=ret連結キー

• 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