Skip to content

737. Sentence Similarity II 👍

  • Time: $O(\max(|\texttt{sentence1}|, |\texttt{sentence2}|) \cdot |\texttt{similarPairs}|)$
  • Space: $O(|\texttt{similarPairs}|)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution {
 public:
  bool areSentencesSimilarTwo(vector<string>& words1, vector<string>& words2,
                              vector<vector<string>>& pairs) {
    if (words1.size() != words2.size())
      return false;

    // graph[key] := all the similar words of key
    unordered_map<string, unordered_set<string>> graph;

    for (const vector<string>& pair : pairs) {
      graph[pair[1]].insert(pair[0]);
      graph[pair[0]].insert(pair[1]);
    }

    for (int i = 0; i < words1.size(); ++i) {
      if (words1[i] == words2[i])
        continue;
      if (!graph.contains(words1[i]))
        return false;
      if (!dfs(graph, words1[i], words2[i], {}))
        return false;
    }

    return true;
  }

 private:
  bool dfs(const unordered_map<string, unordered_set<string>>& graph,
           const string& source, const string& target,
           unordered_set<string>&& seen) {
    if (graph.at(source).contains(target))
      return true;

    seen.insert(source);

    for (const string& child : graph.at(source)) {
      if (seen.contains(child))
        continue;
      if (dfs(graph, child, target, std::move(seen)))
        return true;
    }

    return false;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution {
  public boolean areSentencesSimilarTwo(String[] words1, String[] words2,
                                        List<List<String>> pairs) {
    if (words1.length != words2.length)
      return false;

    // graph[key] := all the similar words of key
    Map<String, Set<String>> graph = new HashMap<>();

    for (List<String> pair : pairs) {
      graph.putIfAbsent(pair.get(0), new HashSet<>());
      graph.putIfAbsent(pair.get(1), new HashSet<>());
      graph.get(pair.get(1)).add(pair.get(0));
      graph.get(pair.get(0)).add(pair.get(1));
    }

    for (int i = 0; i < words1.length; ++i) {
      if (words1[i].equals(words2[i]))
        continue;
      if (!graph.containsKey(words1[i]))
        return false;
      if (!dfs(graph, words1[i], words2[i], new HashSet<>()))
        return false;
    }

    return true;
  }

  private boolean dfs(Map<String, Set<String>> graph, final String source, final String target,
                      Set<String> seen) {
    if (graph.get(source).contains(target))
      return true;

    seen.add(source);

    for (final String child : graph.get(source)) {
      if (seen.contains(child))
        continue;
      if (dfs(graph, child, target, seen))
        return true;
    }

    return false;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution:
  def areSentencesSimilarTwo(
      self,
      words1: list[str],
      words2: list[str],
      pairs: list[list[str]],
  ) -> bool:
    if len(words1) != len(words2):
      return False

    # graph[key] := all the similar words of key
    graph = collections.defaultdict(set)

    for a, b in pairs:
      graph[a].add(b)
      graph[b].add(a)

    def dfs(word1: str, word2: str, seen: set) -> bool:
      if word1 in graph[word2]:
        return True

      seen.add(word1)

      for child in graph[word1]:
        if child in seen:
          continue
        if dfs(child, word2, seen):
          return True

      return False

    for word1, word2 in zip(words1, words2):
      if word1 == word2:
        continue
      if word1 not in graph:
        return False
      if not dfs(word1, word2, set()):
        return False

    return True