难度: 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%
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 = {}
cnt = itertools.count()
for parent, child in pairs:
if parent not in word_idx:
word_idx[parent] = next(cnt)
if child not in word_idx:
word_idx[child] = next(cnt)
union(word_idx[child], word_idx[parent])
## check if sentences match
for w1, w2 in zip(words1, words2):
if w1 == w2:
continue
if w1 in word_idx:
idx1 = word_idx[w1]
else:
return False
if w2 in word_idx:
idx2 = word_idx[w2]
else:
return False
if find(idx1) != find(idx2):
return False
return True思路 1 - 时间复杂度: O(len(words1) * len(pairs))- 空间复杂度: O(len(pairs))******
其实我们完全没有必要搞一个word_idx,我们只要让我们的uf列表变成一个字典就可以了
需要注意的就是find()函数的写法
beats 94.92%
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
## inititalize parents
uf = {}
def find(w):
if w not in uf:
uf[w] = w
while w in uf and uf[w] != w:
w = uf[w]
return w
## set parents
for p1, p2 in pairs:
w1 = find(p1)
w2 = find(p2)
uf[w1] = w2
## check if sentences match
for w1, w2 in zip(words1, words2):
if w1 == w2:
continue
if find(w1) != find(w2):
return False
return True