C++の同様の文字列グループ

2つの文字列XとYがあるとします。これらは、Xの2つの文字を入れ替えて、Yに等しくなる場合は類似しています。また、2つの文字列XとYは、等しい場合は類似しています。例として、2つの文字列が「tars」と「rats」に似ていると考えてください。tとrを入れ替えると、別の文字列を見つけることができます。「rats」と「arts」は似ていますが、「star」は似ていません。 「tars」、「rats」、または「arts」に似ています。これで、{"tars"、 "rats"、 "arts"}、{"star"}という類似性によって2つの接続されたグループが形成されていることがわかります。ここで、「tars」と「arts」は、類似していなくても同じグループに属しています。したがって、各グループは、その単語がグループ内の他の少なくとも1つの単語と類似している場合にのみ、その単語がグループ内にあるようになっています。文字列のリストAがあるとします。 Aのすべての文字列は、Aの他のすべての文字列のアナグラムです。グループがいくつあるかを確認する必要がありますか？

したがって、入力が["tars"、 "rats"、 "arts"、 "star"]の場合、出力は2

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

• 配列の親を定義する

• 配列ランクを定義する

• 関数getParent（）を定義します。これにはxが必要です

  • parent [x]が-1と同じ場合、-

    • xを返す

  • return parent [x] =getParent（parent [x]）

• 関数unionn（）を定義します。これには、x、y、

  が必要です。

  • parX：=getParent（x）、parY：=getParent（y）

  • parXがparYと同じ場合、-

    • falseを返す

  • ランク[parX]>=ランク[parY]の場合、-

    • ランク[parX]：=ランク[parX]+ランク[parY]

    • parent [parY]：=parX

  • それ以外の場合

    • ランク[parY]：=ランク[parY]+ランク[parX]

    • parent [parX]：=parY

  • trueを返す

• 関数ok（）を定義します。これにはs1、s2、

  が必要です。

  • cnt：=0

  • 初期化i：=0の場合、i

    • s1[i]がs2[i]と等しくない場合、-

      • （cntを1増やします）

    • cnt> 2の場合、-

      • falseを返す

  • trueを返す

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

• ret：=0

• n：=Aのサイズ

• ret：=n

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

• ランク：=サイズnの配列で、これを1で埋めます

• 初期化i：=0の場合、i

  • 初期化j：=i + 1の場合、j

    • ok（A [i]、A [j]）がゼロ以外の場合、-

      • unionn（i、j）がゼロ以外の場合、-

        • （retを1減らします）

• retを返す

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

例

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}
class Solution {
   public:
   vector<int> parent;
   vector<int> rank;
   int getParent(int x){
      if (parent[x] == -1)
      return x;
      return parent[x] = getParent(parent[x]);
   }
   bool unionn(int x, int y){
      int parX = getParent(x);
      int parY = getParent(y);
      if (parX == parY)
      return false;
      if (rank[parX] >= rank[parY]) {
         rank[parX] += rank[parY];
         parent[parY] = parX;
      } else {
         rank[parY] += rank[parX];
         parent[parX] = parY;
      }
      return true;
   }
   bool ok(string& s1, string& s2){
      int cnt = 0;
      for (int i = 0; i < s1.size(); i++) {
         if (s1[i] != s2[i])
         cnt++;
         if (cnt > 2)
         return false;
      }
      return true;
   }
   int numSimilarGroups(vector<string>& A){
      int ret = 0;
      int n = A.size();
      ret = n;
      parent = vector<int>(n, -1);
      rank = vector<int>(n, 1);
      for (int i = 0; i < n; i++) {
         for (int j = i + 1; j < n; j++) {
            if (ok(A[i], A[j])) {
               if (unionn(i, j))
               ret--;
            }
         }
      }
      return ret;
   }
};
main(){
   Solution ob;
   vector<string> v = {"tars","rats","arts","star"};
   cout << (ob.numSimilarGroups(v));
}

入力

{"tars","rats","arts","star"}

出力

2