C++의 유사한 문자열 그룹

<시간/>

두 개의 문자열 X와 Y가 있다고 가정하고 X의 두 글자를 바꿔서 Y와 같게 할 수 있다면 이들은 비슷합니다. 또한 두 문자열 X와 Y는 같으면 비슷합니다. 예를 들어, 두 개의 문자열이 "tars"와 같고 "rats"가 비슷하다고 생각하면 t와 r을 바꾸면 다른 문자열을 찾을 수 있습니다. 이제 "rats"와 "arts"는 비슷하지만 "star"는 그렇지 않습니다. "tars", "rats" 또는 "arts"와 유사합니다. 이제 우리는 이들이 {"tar", "rats", "arts"} 및 {"star"}라는 유사성으로 연결된 두 그룹을 형성한다는 것을 알 수 있습니다. 여기서 "tar"와 "arts"는 유사하지 않더라도 같은 그룹에 속합니다. 따라서 각 그룹은 단어가 그룹의 다른 단어 중 하나 이상과 유사한 경우에만 그룹에 포함됩니다. 문자열 목록 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]이면 -
  - 순위[parX] :=순위[parX] + 순위[parY]
  - 부모[parY] :=parX
- 그렇지 않으면
  - 순위[parY] :=순위[parY] + 순위[parX]
  - 부모[parX] :=parY
- true를 반환
ok() 함수를 정의하면 s1, s2,
가 필요합니다.
- cnt :=0
- initialize i :=0의 경우, i
  - s1[i]가 s2[i]와 같지 않으면 -
    - (cnt를 1씩 증가)
  - cnt> 2이면 -
    - 거짓을 반환
- true를 반환
기본 방법에서 다음을 수행하십시오 -
ret :=0
n :=A의 크기
렛 :=n
parent :=크기가 n인 배열이고 -1로 채웁니다.
rank :=크기가 n인 배열이고 1로 채웁니다.
initialize i :=0의 경우, i
- j 초기화의 경우 :=i + 1, j
  - ok(A[i], A[j])가 0이 아니면 -
    - Unionn(i, j)가 0이 아니면 -
      - (ret 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"}