💬 Discord
Sign In
NeetCode #12LC-734EasyArrays & HashingNC Algo100
← Back to All Problems

#12 · #734 · Sentence Similarity(句子相似性)

📌 Problem Statement & Constraints

Given two sentences sentence1 and sentence2 as arrays of words, and a list of similarPairs of words, determine whether the two sentences are similar: they must have the same length, and each word pair must be either identical or listed as similar. Similarity is not transitive. Constraints: 1 <= length <= 1000, 0 <= similarPairs.length <= 2000.

💡 Core Algorithmic Approaches

  1. First reject sentences of different lengths -- similarity is defined position by position.
  2. Store the similarity relation in a set of ordered pairs, inserting both (a, b) and (b, a) so the lookup is direction-agnostic.
  3. Then zip the two sentences and verify each pair: either the words are equal, or the ordered pair is in the set.
  4. Because the relation is not transitive, a union-find or transitive-closure approach would be wrong here.

💻 Benchmark Python3 Implementation

class Solution:
    def areSentencesSimilar(self, sentence1: List[str], sentence2: List[str],
                            similarPairs: List[List[str]]) -> bool:
        if len(sentence1) != len(sentence2):
            return False
        pairs = set()
        for a, b in similarPairs:
            pairs.add((a, b))              # symmetric relation
            pairs.add((b, a))
        for a, b in zip(sentence1, sentence2):
            if a != b and (a, b) not in pairs:
                return False
        return True

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(p + n): O(p) to build the pair set from similarPairs, then O(n) to check the sentences.
💾 Space Complexity
O(p) for the pair set.

⚠️ Interview Pitfalls & Follow-ups

  • Inserting only one direction: (a, b) does not imply (b, a) in the input format, so both must be stored.
  • Treating similarity as transitive: if a~b and b~c, a is still not similar to c. Union-find would be wrong.
  • Skipping the length check: unequal lengths must return false, not raise or zip-truncate.
  • Comparing with a list of pairs instead of a set: O(p) per lookup, giving O(n*p) overall.