C++의 문장 유사성 II

<시간/>

두 개의 배열 words1, words2가 주어졌다고 가정하고 이들은 문장으로 간주되며 유사한 단어 쌍의 목록은 두 문장이 유사한지 여부를 확인해야 합니다. 따라서 입력이 words1 =["great", "acting", "skills"] 및 words2 =["fine", "drama", "talent"]인 경우 유사한 단어 쌍이 =[["훌륭하다", "좋다"], ["좋다", "좋다"], ["연기","드라마"], ["실력","재능"]].

유사성 관계는 전이적입니다. 예를 들어 "훌륭하다"와 "좋다"가 비슷하고 "좋다"와 "좋다"가 비슷하면 "훌륭하다"와 "좋다"도 비슷합니다. 그리고 유사도도 대칭입니다. 따라서 "Great"와 "fine"이 유사한 것은 "fine"과 동일하고 "Great"는 유사합니다. 단어는 항상 그 자체와 유사합니다. 마지막으로, 문장은 단어 수가 같은 경우에만 유사할 수 있습니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

하나의 상위 맵, 다른 맵 ID를 정의합니다.
getParent() 함수를 정의하면 x가 필요합니다.
x가 부모에 없으면 -
- x를 반환
부모[x] :=getParent(부모[x])
부모 반환[x]
Unionn() 함수를 정의하면, b,
parentA :=getParent(idx[a])
parentB :=getParent(idx[b])
parentA가 parentB와 같으면 -
- 반환
부모[부모A] :=부모B
주요 방법에서 다음을 수행하십시오 -
word1의 크기가 words2의 크기와 같지 않으면 -
- 거짓 반환
n :=단어의 크기1
카운터 :=1
initialize i :=0의 경우, i
- words1[i]이 idx에 없으면 -
  - idx[words1[i]] :=카운터, 카운터를 1 증가
initialize i :=0의 경우, i
- words2[i]가 idx에 없으면 -
  - idx[words2[i]] :=카운터, 카운터를 1 증가
initialize i :=0, i <쌍의 크기일 때 업데이트(i 1만큼 증가), 수행 -
- u :=쌍[i,0]
- v :=쌍[i,1]
- idx에 없으면 -
  - idx[u] :=카운터, 카운터를 1 증가
- v가 idx에 없으면 -
  - idx[v] :=카운터, 카운터를 1 증가
- 유니온(u, v)
initialize i :=0의 경우, i
- 유 :=단어1[i]
- v :=단어2[i]
- u가 v와 같으면 -
  - 다음 부분은 무시하고 다음 반복으로 건너뜁니다.
- getParent(idx[u])가 getParent(idx[v])와 같지 않으면 -
  - 거짓 반환
true를 반환

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   unordered_map<int, int> parent;
   unordered_map<string, int> idx;
   int getParent(int x){
      if (!parent.count(x))
         return x;
      return parent[x] = getParent(parent[x]);
   }
   void unionn(string a, string b){
      int parentA = getParent(idx[a]);
      int parentB = getParent(idx[b]);
      if (parentA == parentB)
         return;
      parent[parentA] = parentB;
   }
   bool areSentencesSimilarTwo(vector<string>& words1, vector<string>& words2, vector<vector<string> >& pairs){
      if (words1.size() != words2.size())
         return false;
      int n = words1.size();
      int counter = 1;
      for (int i = 0; i < n; i++) {
         if (!idx.count(words1[i])) {
            idx[words1[i]] = counter++;
         }
      }
      for (int i = 0; i < n; i++) {
         if (!idx.count(words2[i])) {
            idx[words2[i]] = counter++;
         }
      }
      for (int i = 0; i < pairs.size(); i++) {
         string u = pairs[i][0];
         string v = pairs[i][1];
         if (!idx.count(u)) {
            idx[u] = counter++;
         }
         if (!idx.count(v)) {
            idx[v] = counter++;
         }
         unionn(u, v);
      }
      for (int i = 0; i < n; i++) {
         string u = words1[i];
         string v = words2[i];
         if (u == v)
            continue;
         if (getParent(idx[u]) != getParent(idx[v]))
         return false;
      }
      return true;
   }
};
main(){
   Solution ob;
   vector<string> v = { "great", "acting", "skills" }, v1 = { "fine", "drama", "talent" };
   vector<vector<string> > v2 = { { "great", "good" }, { "fine", "good" }, { "drama", "acting" }, { "skills", "talent" } };
   cout << (ob.areSentencesSimilarTwo(v, v1, v2));
}

입력

{"great","acting","skills"}, {"fine","drama","talent"},
{{"great","good"},{"fine","good"},{"drama","acting"},{"skills","talent"}}

C++의 문장 유사성 II

예시

입력

출력