# 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& words1, vector& words2, vector>& pairs) { if (words1.size() != words2.size()) return false; // graph[key] := all similar words of key unordered_map> graph; for (const auto& pair : pairs) { graph[pair].insert(pair); graph[pair].insert(pair); } for (int i = 0; i < words1.size(); ++i) { if (words1[i] == words2[i]) continue; if (!graph.count(words1[i])) return false; if (!dfs(graph, words1[i], words2[i], {})) return false; } return true; } private: bool dfs(const unordered_map>& graph, const string& source, const string& target, unordered_set&& seen) { if (graph.at(source).count(target)) return true; seen.insert(source); for (const string& child : graph.at(source)) { if (seen.count(child)) continue; if (dfs(graph, child, target, 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> pairs) { if (words1.length != words2.length) return false; // graph[key] := all similar words of key Map> graph = new HashMap<>(); for (List 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> graph, final String source, final String target, Set 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 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 similar words of key graph = 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