सी++ में समान स्ट्रिंग समूह

मान लीजिए कि हमारे पास दो स्ट्रिंग्स एक्स और वाई हैं, ये समान हैं यदि हम एक्स के दो अक्षरों को स्वैप कर सकते हैं, ताकि यह वाई के बराबर हो। साथ ही दो स्ट्रिंग्स एक्स और वाई समान हैं यदि वे बराबर हैं। एक उदाहरण के रूप में, विचार करें, दो तार "टार" की तरह हैं और "चूहे" समान हैं, यदि हम टी और आर को स्वैप करते हैं, तो हम एक और पा सकते हैं, अब "चूहे" और "कला" समान हैं, लेकिन "स्टार" नहीं है "टार", "चूहों", या "कला" के समान। अब हम देख सकते हैं, ये समानता से दो जुड़े हुए समूह बनाते हैं:{"tars", "rats", "arts"} और {"star"}। यहां "टार" और "कला" एक ही समूह में हैं, भले ही वे समान न हों। तो, प्रत्येक समूह ऐसा है कि एक शब्द समूह में है यदि और केवल यदि वह समूह में कम से कम एक अन्य शब्द के समान है। मान लीजिए कि हमारे पास स्ट्रिंग्स की एक सूची ए है। ए में प्रत्येक स्ट्रिंग ए में हर दूसरे स्ट्रिंग का विपर्यय है। हमें यह पता लगाना है कि कितने समूह हैं?

इसलिए, यदि इनपुट ["tars",,"rats",,"arts",,"star"] जैसा है, तो आउटपुट 2

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• सरणी पैरेंट को परिभाषित करें

• एक सरणी रैंक परिभाषित करें

• getParent() फ़ंक्शन को परिभाषित करें, इसमें x लगेगा,

  • अगर माता-पिता [x] -1 के समान है, तो -

    • वापसी x

  • वापसी माता-पिता [x] =getParent (माता-पिता [x])

• एक फ़ंक्शन को परिभाषित करें Unionn(), इसमें x, y,

  लगेगा

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

  • यदि parX, parY के समान है, तो -

    • झूठी वापसी

  • अगर रैंक [parX]>=रैंक [parY], तो −

    • रैंक [parX]:=रैंक [parX] + रैंक [parY]

    • माता-पिता [parY] :=parX

  • अन्यथा

    • रैंक [parY] :=रैंक [parY] + रैंक [parX]

    • पैरेंट [parX] :=parY

  • सही लौटें

• फ़ंक्शन को परिभाषित करें ठीक (), इसमें s1, s2,

  लगेगा

  • सीएनटी:=0

  • इनिशियलाइज़ i :=0 के लिए, जब i

    • अगर s1[i], s2[i] के बराबर नहीं है, तो -

      • (cnt 1 से बढ़ाएँ)

    • अगर cnt> 2, तो -

      • झूठी वापसी

  • सही लौटें

• मुख्य विधि से, निम्न कार्य करें -

• रिट:=0

• n :=A का आकार

• रिट :=n

• पैरेंट :=आकार n की एक सरणी, और इसे -1 से भरें

• रैंक:=आकार n की एक सरणी, और इसे 1 से भरें

• इनिशियलाइज़ i :=0 के लिए, जब i

  • इनिशियलाइज़ j :=i + 1 के लिए, जब j

    • अगर ठीक है (ए [i], ए [जे]) शून्य नहीं है, तो -

      • अगर Unionn(i, j) गैर-शून्य है, तो -

        • (रिटर्न 1 से घटाएं)

• वापसी रिट

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

#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