Home
Algorithms Data Structures Interview Experiences
Amazon Google Facebook Microsoft Apple Netflix
Play 2048 How to

LeetCode Solutions

734. Sentence Similarity

Time: $O(\max(|\texttt{sentence1}|, |\texttt{sentence2}|) + |\texttt{similarPairs}|)$

Space: $O(|\texttt{similarPairs}|)$

			


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 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.count(sentence1[i]))
        return false;
      if (!map[sentence1[i]].count(sentence2[i]))
        return false;
    }

    return true;
  }
};




			


class Solution {
  public boolean areSentencesSimilar(String[] sentence1, String[] sentence2,
                                     List<List<String>> similarPairs) {
    if (sentence1.length != sentence2.length)
      return false;

    // map[key] := all 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;
  }
}




			


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 similar words of key
    map = 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