C++ এ অনুরূপ স্ট্রিং গ্রুপ

ধরুন আমাদের দুটি স্ট্রিং X এবং Y আছে, যদি আমরা X-এর দুটি অক্ষর অদলবদল করতে পারি তাহলে এগুলো একই রকম হবে, যাতে এটি Y সমান হয়। এছাড়াও দুটি স্ট্রিং X এবং Y যদি সমান হয়। একটি উদাহরণ হিসাবে, বিবেচনা করুন, দুটি স্ট্রিং "tars" এবং "ইঁদুর" একই রকম, যদি আমরা t এবং r অদলবদল করি, তাহলে আমরা আরেকটি খুঁজে পেতে পারি, এখন "ইঁদুর" এবং "আর্টস" একই রকম, কিন্তু "তারকা" নয় "টারস", "ইঁদুর" বা "আর্টস" এর মতো। এখন আমরা দেখতে পাচ্ছি, এগুলি সাদৃশ্য দ্বারা দুটি সংযুক্ত গোষ্ঠী গঠন করে:{"tars", "rats", "arts"} এবং {"star"}। এখানে "tars" এবং "আর্টস" একই গ্রুপে রয়েছে যদিও তারা একই রকম নয়। সুতরাং, প্রতিটি গ্রুপ এমন যে একটি শব্দ গ্রুপে থাকে যদি এবং শুধুমাত্র যদি এটি গ্রুপের অন্তত একটি অন্য শব্দের মতো হয়। ধরুন আমাদের স্ট্রিং এর একটি তালিকা A আছে। A এর প্রতিটি স্ট্রিং A এর প্রতিটি অন্য স্ট্রিংয়ের একটি অ্যানাগ্রাম। আমাদের খুঁজে বের করতে হবে সেখানে কতটি গ্রুপ আছে?

সুতরাং, যদি ইনপুটটি ["tars","rats","arts","star"] এর মত হয়, তাহলে আউটপুট হবে 2

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• একটি অ্যারে অভিভাবক সংজ্ঞায়িত করুন

• একটি অ্যারে র‍্যাঙ্ক সংজ্ঞায়িত করুন

• একটি ফাংশন সংজ্ঞায়িত করুন getParent(), এটি x,

  লাগবে

  • যদি অভিভাবক[x] -1 এর মত হয়, তাহলে −

    • রিটার্ন x

  • রিটার্ন প্যারেন্ট[x] =getParent(অভিভাবক[x])

• একটি ফাংশন unionn() সংজ্ঞায়িত করুন, এটি x, y,

  লাগবে

  • parX :=getParent(x), parY :=getParent(y)

  • যদি parX parY এর মত হয়, তাহলে −

    • মিথ্যা ফেরত দিন

  • যদি rank[parX]>=rank[parY] হয়, তাহলে −

    • rank[parX] :=rank[parX] + rank[parY]

    • পিতামাতা[parY] :=parX

  • অন্যথায়

    • rank[parY] :=rank[parY] + rank[parX]

    • অভিভাবক[parX] :=parY

  • প্রত্যাবর্তন সত্য

• একটি ফাংশন ঠিক করুন (), এটি s1, s2,

  লাগবে

  • cnt :=0

  • আরম্ভ করার জন্য i :=0, যখন i

    • যদি s1[i] s2[i] এর সমান না হয়, তাহলে −

      • (1 দ্বারা cnt বাড়ান)

    • যদি cnt> 2, তাহলে −

      • মিথ্যা ফেরত দিন

  • প্রত্যাবর্তন সত্য

• প্রধান পদ্ধতি থেকে, নিম্নলিখিতগুলি করুন -

• ret :=0

• n :=A

  এর আকার

• ret :=n

• parent :=n আকারের একটি অ্যারে, এবং এটি -1 দিয়ে পূরণ করুন

• rank :=n আকারের একটি অ্যারে, এবং এটি 1 দিয়ে পূরণ করুন

• আরম্ভ করার জন্য i :=0, যখন i

  • j শুরু করার জন্য :=i + 1, যখন j করুন

    • যদি ok(A[i], A[j]) অ-শূন্য হয়, তাহলে −

      • যদি unionn(i, j) অ-শূন্য হয়, তাহলে −

        • (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