1. Using Hash Map and Hash Set

Intuition

Two sentences are similar if they have the same length and each pair of corresponding words is either identical or defined as similar in the given pairs. To check similarity efficiently, we build a lookup structure: a hash map where each word maps to a set of its similar words. Since similarity is symmetric, we add both directions for each pair. Then we simply iterate through both sentences and verify each word pair using wordToSimilarWords.

Algorithm

  1. If the two sentences have different lengths, return false.
  2. Build a hash map wordToSimilarWords where each word maps to a hash set of its similar words.
    • For each pair (word1, word2), add word2 to word1's set and word1 to word2's set.
  3. For each index i in the sentences:
    • If sentence1[i] equals sentence2[i], continue.
    • If sentence2[i] is in the similar words set of sentence1[i], continue.
    • Otherwise, return false (words are not similar).
  4. Return true (all word pairs are similar).
class Solution(object):
    def areSentencesSimilar(self, sentence1, sentence2, similarPairs):
        if len(sentence1) != len(sentence2):
            return False
        
        wordToSimilarWords = defaultdict(set)

        for word1, word2 in similarPairs:
            wordToSimilarWords[word1].add(word2)
            wordToSimilarWords[word2].add(word1)

        for i in range(len(sentence1)):
            if sentence1[i] == sentence2[i] or sentence2[i] in wordToSimilarWords[sentence1[i]]:
                continue
            return False
        
        return True

Time & Space Complexity

  • Time complexity: O((n+k)⋅m)O((n + k) \cdot m)
  • Space complexity: O(k⋅m)O(k\cdot m)

Where nn is the number of words in sentence1 and sentence2, kk is the length of similarPairs, and mm is the average length of words in sentence1 as well as similarPairs.