Skip to content

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<string>& sentence1, vector<string>& sentence2,
                           vector<vector<string>>& similarPairs) {
    if (sentence1.size() != sentence2.size())
      return false;

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

    for (const vector<string>& 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.contains(sentence1[i]))
        return false;
      if (!map[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
22
23
24
25
26
27
28
class Solution {
  public boolean areSentencesSimilar(String[] sentence1, String[] sentence2,
                                     List<List<String>> similarPairs) {
    if (sentence1.length != sentence2.length)
      return false;

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

    for (List<String> 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
22
23
24
25
26
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