# 734. Sentence Similarity¶

• Time: $O(\max(|\texttt{sentence1}|, |\texttt{sentence2}|) + |\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 class Solution { public: bool areSentencesSimilar(vector& sentence1, vector& sentence2, vector>& similarPairs) { if (sentence1.size() != sentence2.size()) return false; // map[key] := all the similar words of key unordered_map> map; for (const vector& pair : similarPairs) { map[pair[1]].insert(pair[0]); map[pair[0]].insert(pair[1]); } for (int i = 0; i < sentence1.size(); ++i) { if (sentence1[i] == sentence2[i]) continue; if (!map.count(sentence1[i])) return false; if (!map[sentence1[i]].count(sentence2[i])) return false; } return true; } }; 
  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 class Solution { public boolean areSentencesSimilar(String[] sentence1, String[] sentence2, List> similarPairs) { if (sentence1.length != sentence2.length) return false; // map[key] := all the similar words of key Map> map = new HashMap<>(); for (List pair : similarPairs) { map.putIfAbsent(pair.get(0), new HashSet<>()); map.putIfAbsent(pair.get(1), new HashSet<>()); map.get(pair.get(1)).add(pair.get(0)); map.get(pair.get(0)).add(pair.get(1)); } for (int i = 0; i < sentence1.length; ++i) { if (sentence1[i].equals(sentence2[i])) continue; if (!map.containsKey(sentence1[i])) return false; if (!map.get(sentence1[i]).contains(sentence2[i])) return false; } return true; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 class Solution: def areSentencesSimilar(self, sentence1: List[str], sentence2: List[str], similarPairs: List[List[str]]) -> bool: if len(sentence1) != len(sentence2): return False # map[key] := all the similar words of key map = collections.defaultdict(set) for a, b in similarPairs: map[a].add(b) map[b].add(a) for word1, word2 in zip(sentence1, sentence2): if word1 == word2: continue if word1 not in map: return False if word2 not in map[word1]: return False return True