Sentence Similarity II

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

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

Note that the similarity relationistransitive. 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 sentenceswords1 = ["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 likewords1 = ["great"]can never be similar towords2 = ["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]

  .

分析

dfs：建图，然后2点直接不到的话，loop w1的邻居n,试着从n到w2

每俩单词一个新的路径找，所以需要新visited？

一定注意每俩单词的visited都要New set（）！！！！！！不能总体的visited，错很久

class Solution:
    def areSentencesSimilarTwo(self, words1: List[str], words2: List[str], pairs: List[List[str]]) -> bool:
        if len(words1) != len(words2):
            return False
        g = collections.defaultdict(list)
        for w1,w2 in pairs:
            g[w1].append(w2)
            g[w2].append(w1)

        ll = len(words1)
        for i, j in zip(words1,words2):
            if not self.dfs(i,j,g,set()): #不同连通子集，每次都需要new不同set，不能一个set
                return False
        return True    


    def dfs(self,w1,w2,g,visited):
        if w1 == w2:
            return True 
        if w1 in visited:
            return False
        visited.add(w1)

        if w1 in g:
            for n in g[w1]:
                if self.dfs(n,w2,g,visited):
                    return True
        return False

BFS

还是要建图，但是和DFS不同，dfs每俩单词一次新搜索，这里总体bfs一次，每一群单词组用dict[w] = 群号.类似于所有单词归类了自己的群

然后w1,w2比较在不在一个群或者是否相等。

class Solution:
    def areSentencesSimilarTwo(self, words1: List[str], words2: List[str], pairs: List[List[str]]) -> bool:
        if len(words1) != len(words2):
            return False
        g = collections.defaultdict(list)
        for w1,w2 in pairs:
            g[w1].append(w2)
            g[w2].append(w1)

        levelnum = collections.defaultdict(int)

        level = 0
        for w in g:            
            if w in levelnum:
                continue
            level += 1              
            q = [w]
            while q:
                cur = q.pop()
                levelnum[cur] = level
                for n in g[cur]:
                    if n not in levelnum:
                        q.append(n)

        for i, j in zip(words1,words2):
            if i == j:
                continue
            if levelnum[i] !=levelnum[j]:
                return False
        return True

Union find

father 是str:str的dict

注意最后比较是find(x) !=find(y) 不能直接f[x]!=f[y]

这里find function写法注意，同时dict赋值是f[fi] = fj #不能是fi = f[fj] key error

class Solution:
    def areSentencesSimilarTwo(self, words1: List[str], words2: List[str], pairs: List[List[str]]) -> bool:
        if len(words1) != len(words2):
            return False
        words = set()        

        f = {}#str 指向自己

        def find(x):
            if x in f:
                return find(f[x])
            return x

        for i,j in pairs:
            fi = find(i)
            fj = find(j)
            if fi!=fj:
                f[fi] = fj #不能是fi = f[fj] key error

        for i,j in zip(words1,words2):
            if i == j:
                continue
            if find(i) != find(j):#不是f[i] !=f[j] 会key error
                return False
        return True