# Sentence Similarity II

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]`

  .

分析

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
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://nataliekung.gitbook.io/ladder_code/dfs/sentence-similarity-ii.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.