# LeetCode: 737. 句子相似性II¶

## 1、题目描述¶

• words1 and words2 的长度不会超过 1000
• pairs 的长度不会超过 2000
• 每个pairs[i] 的长度为 2
• 每个 words[i]pairs[i][j] 的长度范围为 [1, 20]

## 2、解题思路¶

• 使用并查集将相似的单词放到同一个集合中
class DFU:
def __init__(self, length):
self.data = list(range(length))

def find(self, x):
if self.data[x] != x:
self.data[x] = self.find(self.data[x])
return self.data[x]

def union(self, x, y):
xp = self.find(x)
yp = self.find(y)
if xp != yp:
self.data[xp] = yp

def count(self):
res = 0
for index, i in enumerate(self.data):
if index == i:
res += 1
return res

class Solution:
def areSentencesSimilarTwo(self, words1: List[str], words2: List[str], pairs: List[List[str]]) -> bool:
if len(words1) != len(words2):
return False
mapping = {val: index for index, val in enumerate(set([item for sublist in pairs for item in sublist]))}
d = DFU(len(mapping))
for x, y in pairs:
d.union(mapping[x], mapping[y])

for w1, w2 in zip(words1, words2):
if w1 == w2:
continue
if (w1 != w2 and (w1 not in mapping or w2 not in mapping)) or (d.find(mapping[w1]) != d.find(mapping[w2])):
return False
return True