C++で辞書式順序で最小の同等の文字列

同じ長さの文字列AとBがあるとすると、A[i]とB[i]は同等の文字であると言えます。したがって、たとえば、A="abc"およびB="cde"の場合、'a' ='c'、'b'='d'および'c'='e'になります。同等の文字は、あらゆる同等関係の通常の規則に従います：

• 再帰性：'a' ='a'

• 対称性：'a'='b'は'b'='a'

  を意味します

• 推移性：'a'='b'および'b'='c'は'a'='c'を意味します

たとえば、上記のAとBの同等性情報を考えると、S ="eed"、 "acd"、および "aab"は同等の文字列であり、"aab"は辞書式順序で最小のSの同等の文字列です。 AとBからの同等性情報を使用した、辞書式に最小のSの同等の文字列。この方法で形成できるすべての単語を辞書式順序で返します。

したがって、入力がA =「パーカー」、B =「モリス」、S =「パーサー」の場合、出力は「makkek」になります。これは、AとBの同等性情報に基づいて、それらの文字を[m、p]、[a、o]、[k、r、s]、[e、i]としてグループ化できるためです。したがって、各グループの文字は同等であり、辞書式順序でソートされます。したがって、答えは「makkek」です。

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

• 親と呼ばれる配列を作成します

• getParent（）というメソッドを定義します。これは文字x

  を取ります

• parent [x –「a」のASCII]が-1の場合、x –「a」のASCIIを返します

• parent [x –「a」のASCII]：=getParent（「a」のASCII + parent [x –「a」のASCII]）

• 親を返す[x–「a」のASCII]

• union（）という別のメソッドを作成します。これにはaとbが必要です

• parentA：=getParent（a）、およびparent：=getParent（b）

• したがって、parentA =parentの場合、parentA

• メインの方法から、次のようにします-

• 親：=サイズ26の配列を設定し、-1を使用してこれを埋めます

• 0から25の範囲のiの場合

  • union（A [i]、B [i]）

    を実行します

• 空白の文字列を1つ作成するret

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

  • ret：=ret + getParent（S [i]）+‘a’

• retを返す

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

例

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   vector <int> parent;
   int getParent(char x){
      //cout << x << "-- " << x-'a' << endl;
      if(parent[x - 'a'] == -1) return x - 'a';
      return parent[x - 'a'] = getParent('a' + parent[x - 'a']);
   }
   void unionn(char a, char b){
      int parentA = getParent(a);
      int parentB = getParent(b);
      if(parentA == parentB) return;
      if(parentA < parentB){
         parent[parentB] = parentA;
      }else{
         parent[parentA] = parentB;
      }
   }
   string smallestEquivalentString(string A, string B, string S) {
      parent = vector <int>(26, -1);
      for(int i = 0; i < A.size(); i++){
         unionn(A[i], B[i]);
      }
      string ret = "";
      for(int i = 0; i < S.size(); i++){
         ret += getParent(S[i]) + 'a';
      }
      return ret;
   }
};
main(){
   Solution ob;
   cout <<
   (ob.smallestEquivalentString("parker","morris","parser"));
}

入力

"parker"
"morris"
"parser"

出力

makkek