Sentence Similarity

How it works

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.

Steps

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).

Complexity

• Time complexity: O((n + k) × m)
• Space complexity: O(k × m)

Where n is the number of words in sentence1 and sentence2, k is the length of similarPairs, and m is the average length of words in sentence1 as well as similarPairs.

Things to watch for

Forgetting That Similarity Is Symmetric

When building the lookup structure, a common mistake is only adding one direction of the similarity relationship. If (word1, word2) is a similar pair, then word2 should be accessible from word1 AND word1 should be accessible from word2. Failing to add both directions will cause false negatives when words appear in opposite positions.

Not Checking for Equal Words First

A word is always similar to itself, even if it does not appear in any similarity pair. Forgetting to check if sentence1[i] == sentence2[i] before consulting the similarity map will incorrectly return false for identical words that happen to not be in the pairs list.

from collections import defaultdict

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

class Solution {
public:
    bool areSentencesSimilar(vector<string>& sentence1, vector<string>& sentence2,
                             vector<vector<string>>& similarPairs) {
        if (sentence1.size() != sentence2.size()) {
            return false;
        }
        unordered_map<string, unordered_set<string>> wordToSimilarWords;
        for (auto& pair : similarPairs) {
            wordToSimilarWords[pair[0]].insert(pair[1]);
            wordToSimilarWords[pair[1]].insert(pair[0]);
        }

        for (int i = 0; i < sentence1.size(); i++) {
            // If the words are equal, continue.
            if (sentence1[i] == sentence2[i]) {
                continue;
            }
            // If the words form a similar pair, continue.
            if (wordToSimilarWords[sentence1[i]].count(sentence2[i])) {
                continue;
            }
            return false;
        }

        return true;
    }
};