> For the complete documentation index, see [llms.txt](https://protegejj.gitbook.io/algorithm-practice/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://protegejj.gitbook.io/algorithm-practice/leetcode/graph/737-sentence-similarity-ii.md).

# 737 Sentence Similarity II

## 737. [Sentence Similarity II](https://leetcode.com/problems/sentence-similarity-ii/description/)

## 1. Question

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

## 2. Implementation

**(1) DFS**

```java
class Solution {
    public boolean areSentencesSimilarTwo(String[] words1, String[] words2, String[][] pairs) {
        if (words1.length != words2.length) {
            return false;
        }

        Map<String, Set<String>> graph = new HashMap<>();

        for (String[] pair : pairs) {
            graph.putIfAbsent(pair[0], new HashSet<>());
            graph.putIfAbsent(pair[1], new HashSet<>());

            graph.get(pair[0]).add(pair[1]);
            graph.get(pair[1]).add(pair[0]);
        }

        for (int i = 0; i < words1.length; i++) {
            if (words1[i].equals(words2[i])) {
                continue;
            }

            if (!graph.containsKey(words1[i]) || !graph.containsKey(words2[i])) {
                return false;
            }
            Set<String> visited = new HashSet<>();

            if (!dfs(words1[i], words2[i], graph, visited)) {
                return false;
            }
        }
        return true;
    }

    public boolean dfs(String startWord, String endWord, Map<String, Set<String>> graph, Set<String> visited) {
        if (graph.get(startWord).contains(endWord)) {
            return true;
        }

        if (visited.contains(startWord)) {
            return false;
        }

        visited.add(startWord);
        for (String nextWord : graph.get(startWord)) {
            if (dfs(nextWord, endWord, graph, visited)) {
                return true;
            }
        }
        return false;
    }
}
```

**（2) Union Find**

思路:

(1) 用union find的关键就是要给每个pair里的word分配一个unique id，然后用map存string到id的关系

(2) 在遍历words1和words2，如果map里面没有words1或words2当前的词或者通过find我们发现当前word1和word2不在一个集合里，return false

```java
class Solution {
    public boolean areSentencesSimilarTwo(String[] words1, String[] words2, String[][] pairs) {
        if (words1.length != words2.length) {
            return false;
        }

        UnionFind uf = new UnionFind(2 * pairs.length);

        Map<String, Integer> map = new HashMap<>();
        int id = 0;

        for (String[] pair : pairs) {
            for (String word : pair) {
                if (!map.containsKey(word)) {
                    map.put(word, id);
                    ++id;
                }
            }

            uf.union(map.get(pair[0]), map.get(pair[1]));
        }


        for (int i = 0; i < words1.length; i++) {
            String word1 = words1[i];
            String word2 = words2[i];

            if (word1.equals(word2)) {
                continue;
            }

            if (!map.containsKey(word1) || !map.containsKey(word2) || uf.find(map.get(word1)) != uf.find(map.get(word2))) {
                return false;
            }
        }
        return true;
    }

    class UnionFind {
        int[] sets;
        int[] size;
        int count;

        public UnionFind(int n) {
            sets = new int[n];
            size = new int[n];
            count = n;

            for (int i = 0; i < n; i++) {
                sets[i] = i;
                size[i] = 1;
            }
        }

        public int find(int node) {
            while (node != sets[node]) {
                node = sets[node];
            }
            return node;
        }

        public void union(int i, int j) {
            int node1 = find(i);
            int node2 = find(j);

            if (node1 == node2) {
                return;
            }

            if (size[node1] < size[node2]) {
                sets[node1] = node2;
                size[node2] += size[node1];
            }
            else {
                sets[node2] = node1;
                size[node1] += size[node2];
            }
            --count;
        }
    }
}
```

## 3. Time & Space Complexity

DFS: 时间复杂度O(nk), 其中n为words的长度， k为pairs的长度，空间复杂度O(k)

Union Find: 时间复杂度O(k + n), 空间复杂度O(k)