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
- Transitivity means the words partition into equivalence classes, which is exactly what union-find computes.
- Union every pair in
similarPairs. - Then each position needs the two words to be in the same class (or identical).
- 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.