C++でスワップする最小の文字列

文字列sと、文字列ペア内のインデックスのペアの配列を指定したとします。ここで、pairs [i] =[a、b]は、文字列の2つのインデックス（0-インデックス）を示します。指定されたペアのインデックスの任意のペアで、必要に応じて何度でも文字を交換できます。スワップを使用した後にsを変更できる辞書式最小の文字列を見つける必要があります。したがって、入力がs =“ dcab”およびpairs =[[0,3]、[1,2]]のような場合、出力は“ bacd”になります。 s[0]とs[3]、s ="bcad"を交換してから、s[1]とs[2]、s="bacd"を交換します。

これを解決するには、次の手順に従います-

• n：=配列のサイズ、親：=サイズnの配列を作成し、これに-1を入力します

• サイズnのretという文字列を作成し、これに*

  を入力します。

• 0からペアのサイズまでの範囲のiの場合

  • u：=ペア[i、0]およびv：=ペア[i、1]

  • uの親がvの親と同じである場合は、次の反復にスキップします

  • parent [uの親]：=vの親

• サイズnの配列arr1を定義します

• 0からn– 1の範囲のiの場合：s[i]をarr[parent of i]

  に挿入します

• 0からn– 1の範囲のiの場合：右から値を読み取ってarr[i]をソートします

• 0からn– 1 −

  の範囲のiの場合

  • ret [i]：=arr1[iの親]の最後のエントリ

  • arr1[iの親]から最後のノードを削除します

例（C ++）

理解を深めるために、次の実装を見てみましょう-

class Solution {
public:
   vector <int> parent;
   int getParent(int x){
      if(parent[x] == -1) return x;
      return parent[x] = getParent(parent[x]);
   }
   string smallestStringWithSwaps(string s, vector<vector<int>>& pairs) {
      int n = s.size();
      parent = vector <int>(n, -1);
      string ret(n, '*');
      for(int i = 0; i < pairs.size(); i++){
         int u = pairs[i][0];
         int v = pairs[i][1];
         if(getParent(u) == getParent(v)) continue;
         parent[getParent(u)] = getParent(v);
      }
      vector < char > arr1[n];
      for(int i = 0; i < n; i++){
         arr1[getParent(i)].push_back(s[i]);
      }
      for(int i = 0; i < n; i++){
         sort(arr1[i].rbegin(), arr1[i].rend());
      }
      for(int i = 0; i < n; i++){
         ret[i] = arr1[getParent(i)].back();
         arr1[getParent(i)].pop_back();
      }
      return ret;
   }
};

入力

"dcab"
[[0,3],[1,2]]

出力

"bacd"