Nhóm chuỗi tương tự trong C ++

Giả sử chúng ta có hai chuỗi X và Y, chúng tương tự nhau nếu chúng ta có thể hoán đổi hai chữ cái của X, sao cho nó bằng Y. Ngoài ra, hai chuỗi X và Y cũng tương tự nếu chúng bằng nhau. Ví dụ, hãy xem xét, hai chuỗi giống như "tars" và "mouse" tương tự nhau, nếu chúng ta hoán đổi t và r thì chúng ta có thể tìm thấy một chuỗi khác, bây giờ "mouse" và "Arts" tương tự nhau, nhưng "star" thì không. tương tự như "tars", "mouse", hoặc "Arts". Bây giờ chúng ta có thể thấy, chúng tạo thành hai nhóm được kết nối với nhau theo điểm giống nhau:{"tars", "mouse", "Arts"} và {"star"}. Ở đây "tars" và "thuật" nằm trong cùng một nhóm mặc dù chúng không giống nhau. Vì vậy, mỗi nhóm sao cho một từ nằm trong nhóm nếu và chỉ khi nó tương tự với ít nhất một từ khác trong nhóm. Giả sử chúng ta có một danh sách A gồm các chuỗi. Mọi chuỗi trong A là đảo chữ của mọi chuỗi khác trong A. Chúng ta phải tìm xem có bao nhiêu nhóm?

Vì vậy, nếu đầu vào là ["tars", "mouse", "Arts", "star"], thì đầu ra sẽ là 2

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

Xác định mảng cha mẹ
Xác định thứ hạng mảng
Xác định một hàm getParent (), điều này sẽ lấy x,
- nếu cha [x] giống -1, thì -
  - trả lại x
- return cha [x] =getParent (cha [x])
Xác định một hàm unionn (), hàm này sẽ lấy x, y,
- parX:=getParent (x), parY:=getParent (y)
- nếu parX giống như parY, thì -
  - trả về false
- nếu rank [parX]> =rank [parY] thì -
  - rank [parX]:=rank [parX] + rank [parY]
  - cha [parY]:=parX
- Nếu không
  - rank [parY]:=rank [parY] + rank [parX]
  - cha [parX]:=parY
- trả về true
Xác định một hàm ok (), điều này sẽ lấy s1, s2,
- cnt:=0
- để khởi tạo i:=0, khi i
  - nếu s1 [i] không bằng s2 [i] thì -
    - (tăng cnt lên 1)
  - nếu cnt> 2, thì -
    - trả về false
- trả về true
Từ phương thức chính, thực hiện như sau -
ret:=0
n:=kích thước của A
ret:=n
parent:=một mảng có kích thước n và điền vào giá trị này bằng -1
rank:=một mảng có kích thước n và điền vào đây là 1
để khởi tạo i:=0, khi i
- để khởi tạo j:=i + 1, khi j
  - nếu ok (A [i], A [j]) khác 0 thì -
    - nếu unionn (i, j) khác 0 thì -
      - (giảm ret xuống 1)
trả lại ret

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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));
}

Đầu vào

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

Nhóm chuỗi tương tự trong C ++

Ví dụ

Đầu vào

Đầu ra