Domain 2MediumMEDIUM

Sentence Similarity II

LeetCode problem 737: Sentence Similarity II (medium).

Domain: medium•Updated: 2026-08-31
#Depth-first Search#Union Find

Problem Breakdown

We need to determine if two sentences (words1, words2) are “similar”. Two conditions must be met:

  1. Length Match: The number of words in both sentences must be identical. If not, they cannot be similar.
  2. Word Similarity: For every index ii, the word at that position (words1[i], words2[i]) must either be exactly equal OR belong to a connected component defined by the similarity pairs.

The key properties of this relationship are:

  • Symmetric: If A is similar to B, then B is similar to A.
  • Transitive: If A ~ B and B ~ C, then A ~ C. This implies we can treat words as nodes in a graph where pairs define edges. Similarity exists if two words are in the same connected component (or identical).

Inputs: words1, words2 (lists of strings), pairs (list of word lists representing similarity relations). Output: Boolean (True or False). Constraints/Edge Cases:

  • Length mismatch is an immediate failure.
  • Words in sentences might not appear in any pair; they are only similar if identical to the counterpart.
  • Duplicate pairs (handled naturally by Union-Find).

Intuition

A naive approach would be to check every word pair (words1[i], words2[i]) against all pairs. If we use BFS/DFS for each query, it becomes O(N⋅P)O(N \cdot P) or worse. Since similarity is transitive and symmetric, this structure strongly suggests a Disjoint Set Union (DSU) / Union-Find data structure.

We can build the graph of similar words once using pairs. Each pair (u, v) merges the sets containing u and v. After building all connections:

  1. If two words are identical (words1[i] == words2[i]), they are trivially similar.
  2. If they differ, we check if their roots in the DSU structure are the same.

This reduces the query time to nearly constant amortized time per word pair after an initial build phase.

Approach

  1. Length Check: Immediately return False if lengths of words1 and words2 differ.
  2. Initialize DSU: Create a mapping for all unique words encountered in both sentences and the pairs list to initialize their parent pointers (initially pointing to themselves). This ensures we handle unseen words gracefully as isolated components.
  3. Build Connectivity: Iterate through each pair (u, v) from pairs. Perform a union operation on sets containing u and v. Use path compression for efficiency during lookups.
  4. Validate Sentences: Iterate index ii from 0 to length-1:
    • If words1[i] == words2[i], continue (similar).
    • Otherwise, check if find(words1[i]) equals find(words2[i]). If not, return False.
  5. Success: Return True after the loop completes without mismatches.

Complexity Analysis

  • Time Complexity: O(N+P⋅α(V))O(N + P \cdot \alpha(V)), where NN is total words in sentences (for length check and iteration), PP is number of pairs, α\alpha is inverse Ackermann function (nearly constant). Building the DSU takes linear time with respect to unique vocabulary size.
  • Space Complexity: O(U)O(U), where UU is the number of unique words across sentences and pairs, stored in the parent map for path compression/rank optimization.

Solution

class UnionFind:
    def __init__(self):
        self.parent = {}
    
    def find(self, x):
        if x not in self.parent:
            # If a word hasn't been seen yet (not part of any pair), 
            # it is its own component. Initialize on demand for lazy handling.
            self.parent[x] = x
            return x
        
        root = x
        while root != self.parent[root]:
            root = self.parent[root]
        
        # Path compression: point all nodes along the path directly to root
        curr = x
        while curr != root:
            next_node = self.parent[curr]
            self.parent[curr] = root
            curr = next_node
            
        return root
    
    def union(self, x, y):
        rootX = self.find(x)
        rootY = self.find(y)
        
        if rootX == rootY:
            return
        
        # Simple rank/size optimization is omitted for brevity but 
        # path compression alone gives nearly constant time.
        # We attach one tree to another arbitrarily here.
        self.parent[rootX] = rootY

def areSentencesSimilarII(words1, words2, pairs):
    if len(words1) != len(words2):
        return False
    
    uf = UnionFind()
    
    # Process all similarity relations first
    for u, v in pairs:
        uf.union(u, v)
        
    # Check each word position
    for w1, w2 in zip(words1, words2):
        if w1 == w2:
            continue
        
        rootW1 = uf.find(w1)
        rootW2 = uf.find(w2)
        
        if rootW1 != rootW2:
            return False
            
    return True

# Example usage (commented out for clean submission):
# print(areSentencesSimilarII(["great", "acting"], ["fine", "drama"], [["great","good"],["fine","good"]])) 

Edge Cases Handled

  • Different Sentence Lengths: Checked immediately at the start; returns False.
  • Identical Words in Sentences (w1 == w2): Skipped DSU check, treated as similar.
  • Words Not Present in Pairs: The lazy initialization inside find() ensures words appearing only in sentences are initialized to themselves (isolated components). If they differ from their counterpart and aren’t connected via pairs, the roots will differ correctly returning False.
  • Empty Pairs List: Loop over pairs does nothing; similarity relies solely on exact word matches.
  • Duplicate/Redundant Pairs: Union-Find handles redundant edges naturally (roots already equal).