Code Implementation

class Solution:
    def areSentencesSimilar(self, sentence1, sentence2, similarPairs):
        if len(sentence1) != len(sentence2):
            return False
        similar = set()
        for a, b in similarPairs:
            similar.add((a, b))
            similar.add((b, a))
        for w1, w2 in zip(sentence1, sentence2):
            if w1 != w2 and (w1, w2) not in similar:
                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_set<string> similar;
        for (auto& pair : similarPairs) {
            similar.insert(pair[0] + "#" + pair[1]);
            similar.insert(pair[1] + "#" + pair[0]);
        }
        for (int i = 0; i < sentence1.size(); ++i) {
            if (sentence1[i] != sentence2[i] && similar.find(sentence1[i] + "#" + sentence2[i]) == similar.end()) {
                return false;
            }
        }
        return true;
    }
};
      

class Solution {
    public boolean areSentencesSimilar(String[] sentence1, String[] sentence2, List<List<String>> similarPairs) {
        if (sentence1.length != sentence2.length) return false;
        Set<String> similar = new HashSet<>();
        for (List<String> pair : similarPairs) {
            similar.add(pair.get(0) + "#" + pair.get(1));
            similar.add(pair.get(1) + "#" + pair.get(0));
        }
        for (int i = 0; i < sentence1.length; ++i) {
            if (!sentence1[i].equals(sentence2[i]) && !similar.contains(sentence1[i] + "#" + sentence2[i])) {
                return false;
            }
        }
        return true;
    }
}
      

var areSentencesSimilar = function(sentence1, sentence2, similarPairs) {
    if (sentence1.length !== sentence2.length) return false;
    const similar = new Set();
    for (const [a, b] of similarPairs) {
        similar.add(a + "#" + b);
        similar.add(b + "#" + a);
    }
    for (let i = 0; i < sentence1.length; i++) {
        if (sentence1[i] !== sentence2[i] && !similar.has(sentence1[i] + "#" + sentence2[i])) {
            return false;
        }
    }
    return true;
};
      

Problem Description

Given two sentences, each represented as a list of words (sentence1 and sentence2), and a list of word pairs (similarPairs), determine if the two sentences are similar. Two words are considered similar if they are the same word or if they appear together as a pair in similarPairs. The similarity relation is symmetric but not transitive. The sentences are similar only if they have the same length and every corresponding pair of words is similar.

• Each input sentence is an array of strings.
• Each pair in similarPairs consists of two strings.
• Similarity is symmetric: if (a, b) is in similarPairs, then (b, a) is also similar.
• The sentences must have the same length to be similar.
• Do not reuse elements from similarPairs; each comparison is independent.

Thought Process

To solve this problem, the first step is to compare the lengths of the two sentences. If they are not the same, they cannot be similar. Next, for each corresponding pair of words, check if they are either identical or listed as similar in similarPairs.

A brute-force solution would check every pair in similarPairs for each word, which is inefficient. To optimize, we can store all similar pairs in a set for constant-time lookups. This way, we can quickly check if two words are similar without scanning the entire list each time.

The main idea is to use a data structure that allows for fast similarity checking, and to ensure we check every word pair only once.

Solution Approach

• Step 1: Check if sentence1 and sentence2 have the same length. If not, return False immediately.
• Step 2: Build a set containing all pairs from similarPairs in both orders (to account for symmetry).
• Step 3: Iterate through each index of the sentences:
  • If the words at the current index are the same, continue.
  • Otherwise, check if the pair (word1, word2) exists in the set of similar pairs.
  • If neither condition is met, return False.
• Step 4: If all pairs pass the checks, return True.

We use a set for similar pairs because it allows O(1) lookup time, making the solution efficient.

Example Walkthrough

Consider the following example:

• sentence1 = ["great", "acting", "skills"]
• sentence2 = ["fine", "drama", "talent"]
• similarPairs = [["great", "fine"], ["drama", "acting"], ["skills", "talent"]]

Let's walk through the process:

1. Check lengths: both have 3 words, so continue.
2. Build the set of similar pairs:
   • ("great", "fine") and ("fine", "great")
   • ("drama", "acting") and ("acting", "drama")
   • ("skills", "talent") and ("talent", "skills")
3. Compare each pair:
   • Index 0: "great" vs "fine" → found in similar pairs
   • Index 1: "acting" vs "drama" → found in similar pairs
   • Index 2: "skills" vs "talent" → found in similar pairs
4. All pairs are similar, so return True.

Time and Space Complexity

• Brute-force approach:
  • For each word pair, check all similarPairs (O(N * M), where N is the sentence length and M is the number of pairs).
• Optimized approach:
  • Building the set takes O(M).
  • For each word pair, lookup is O(1), so total is O(N).
  • Overall time complexity: O(N + M).
  • Space complexity: O(M) for the set of similar pairs.

Summary

The solution efficiently checks sentence similarity by leveraging a set for fast lookups of similar word pairs. By ensuring both sentences are the same length and every word pair is either identical or marked as similar, we guarantee correctness. The use of a set for O(1) lookups makes the approach both simple and optimal for the problem's constraints.