⚡Flashcard Drill➔
NeetCode #626LC-737MediumGraphs
← Back to All Problems

#626 · #737 · Sentence Similarity II(句子相似性 II)

📌 Problem Statement & Constraints

You are given two sentences as arrays of words and a list of similarPairs. Determine whether the sentences are similar, where similarity is now transitive (if a~b and b~c then a~c). Constraints: 1 <= length <= 1000, 0 <= similarPairs.length <= 2000.

💡 Core Algorithmic Approaches

  1. Transitivity means the words partition into equivalence classes, which is exactly what union-find computes.
  2. Union every pair in similarPairs.
  3. Then each position needs the two words to be in the same class (or identical).
  4. This is the same as Sentence Similarity I except the relation is closed under transitivity.

💻 Benchmark Python3 Implementation

class Solution:
    def areSentencesSimilarTwo(self, sentence1: List[str], sentence2: List[str], similarPairs: List[List[str]]) -> bool:
        if len(sentence1) != len(sentence2):
            return False
        parent = {}

        def find(x: str) -> str:
            parent.setdefault(x, x)
            while parent[x] != x:
                parent[x] = parent[parent[x]]
                x = parent[x]
            return x

        for a, b in similarPairs:
            ra, rb = find(a), find(b)
            if ra != rb:
                parent[ra] = rb            # merge the classes

        for a, b in zip(sentence1, sentence2):
            if a != b and find(a) != find(b):
                return False
        return True

⚡ Complexity Deep Dive

⏱️ Time Complexity
O((p + n) * alpha): effectively linear.
💾 Space Complexity
O(p) for the union-find.

⚠️ Interview Pitfalls & Follow-ups

  • Only checking the direct pairs: the relation is transitive, so a plain set of pairs is insufficient.
  • Forgetting the length check: unequal lengths must return false.
  • Using the pair set from problem 734: that version is not transitive.
  • Not applying path compression: the find operations degrade.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Graphs Problems