C++でカスタム順序に従って文字列を並べ替える方法

小文字の英字のみで構成された2つの文字列 S と T が与えられたとします。S には同じ文字が2回以上現れることはなく、S はあらかじめ何らかの独自の順序(カスタムオーダー)でソートされています。ここで、T の文字を並べ替えて、S の順序と一致するようにするのが課題です。具体的には、S 内で x が y より先に現れるならば、結果の文字列でも x は y より先に現れなければなりません。

例として、S = "cba"、T = "abcd" の場合を考えてみましょう。このとき出力は "cbad" となります。"a"、"b"、"c" はいずれも S に含まれているため、これらの順序は S に従って "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(文字 x を ret に追加)。

  • m[x] := 0 とし、処理済みであることを示します。

• m 内の各ペア it に対して以下を繰り返します。

  • it の値(出現回数)が 0 より大きい場合、

    • i を 0 からその値 - 1 までループさせ、ret に it のキー(文字)を出現回数分だけ連結します。

• ret を返します。

S に含まれる文字はまず優先的に順序通りに配置され、その後、S に含まれない残りの文字が出力の末尾に追加されるという仕組みです。

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

計算量について

このアルゴリズムの時間計算量は O(|S| + |T|) です。T の各文字の頻度を数えるのに |T| 回、S の各文字に対応する文字を ret に追加する処理で合計 |T| 回程度の操作が必要となるためです。空間計算量も O(1)(英小文字26種類分のマップ)と考えることができます。