737. Sentence Similarity II

737. Sentence Similarity II

难度: Medium

刷题内容

原题连接

内容描述

Given two sentences words1, words2 (each represented as an array of strings), and a list of similar word pairs pairs, determine if two sentences are similar.

For example, words1 = ["great", "acting", "skills"] and words2 = ["fine", "drama", "talent"] are similar, if the similar word pairs are pairs = [["great", "good"], ["fine", "good"], ["acting","drama"], ["skills","talent"]].

Note that the similarity relation is transitive. For example, if "great" and "good" are similar, and "fine" and "good" are similar, then "great" and "fine" are similar.

Similarity is also symmetric. For example, "great" and "fine" being similar is the same as "fine" and "great" being similar.

Also, a word is always similar with itself. For example, the sentences words1 = ["great"], words2 = ["great"], pairs = [] are similar, even though there are no specified similar word pairs.

Finally, sentences can only be similar if they have the same number of words. So a sentence like words1 = ["great"] can never be similar to words2 = ["doubleplus","good"].

Note:

The length of words1 and words2 will not exceed 1000.
The length of pairs will not exceed 2000.
The length of each pairs[i] will be 2.
The length of each words[i] and pairs[i][j] will be in the range [1, 20].

解题方案

思路 1
*- 时间复杂度: O(len(words1) * len(pairs))- 空间复杂度: O(len(pairs))*

union_find, 先uf = [i for i in range(2 * len(pairs))]

然后将每一对pair的前一个看成是parent,后一个看成child,然后将他们union起来。并且我们union的是pair里的word在word_idx里面对应的index

最后我们开始比较words1和words2,

  • 如果w1和w2相等,那当前肯定similar
  • 如果w1和w2中任意一个没有在word_idx里面,那说明之前的pairs里面没有出现这个word,并且w1和w2又不相等,说明当前w1和w2肯定不similar
  • 最后,如果find(idx1) != find(idx2),当前w1和w2也不similar

beats 91.95%

```python
class Solution:
def areSentencesSimilarTwo(self, words1, words2, pairs):
"""
:type words1: List[str]
:type words2: List[str]
:type pairs: List[List[str]]
:rtype: bool
"""
if len(words1) != len(words2):
return False

    uf = [i for i in range(2 * len(pairs))]

    def find(x):
        while x != uf[x]:
            uf[x] = uf[uf[x]]
            x = uf[x]
        return x

    def union(x1, x2):
        x1_root = find(x1)
        x2_root = find(x2)
        uf[x1_root] = x2_root

    word_idx = {}
top Created with Sketch.