LeetCode Solutions Blog

Sentence Similarity II

Number: 737

Difficulty: Medium

Paid? Yes

Problem Description

Given two sentences represented as arrays of words and a list of similar word pairs, determine whether the two sentences are similar. Two sentences are considered similar if they have the same length and each pair of corresponding words are similar. Note that similarity is defined as:

A word is always similar to itself.
Similarity is transitive (if word A is similar to word B, and word B is similar to word C, then word A is similar to word C).

Key Insights

The sentences must have the same number of words.
Each word is inherently similar to itself.
Similar pairs define an undirected and transitive relationship which can be modeled as a graph or using a Union Find (Disjoint Set) data structure.
Using Union Find helps efficiently group similar words, allowing us to quickly determine if two words belong to the same similarity set.

Space and Time Complexity

Time Complexity: O(N + M * α(M)) where N is the number of words in the sentences, M is the number of similar pairs, and α(M) is the inverse Ackermann function (nearly constant time). Space Complexity: O(M) for storing the disjoint sets.

Solution

We can solve the problem using a Union Find data structure. First, initialize each word as its own parent. Then, for each pair in similarPairs, perform a union operation to group words that are similar. Finally, iterate over corresponding words in sentence1 and sentence2. For each pair, if the words are different, check whether they belong to the same set (i.e., they have the same root). If not, return false; otherwise, continue. If all word pairs pass the check, return true.

Code Solutions

# Python implementation of Sentence Similarity II using Union Find

class UnionFind:
    def __init__(self):
        # parent dictionary to hold the leader for each word
        self.parent = {}
    
    def find(self, word):
        # if the word is not in the parent map, initialize it as its own parent
        if word not in self.parent:
            self.parent[word] = word
        # perform path compression
        if self.parent[word] != word:
            self.parent[word] = self.find(self.parent[word])
        return self.parent[word]
    
    def union(self, word1, word2):
        # get the root parents of both words
        root1 = self.find(word1)
        root2 = self.find(word2)
        if root1 != root2:
            # merge the two sets: attach root1's tree to root2
            self.parent[root1] = root2

def areSentencesSimilarTwo(sentence1, sentence2, similarPairs):
    # check if both sentences have the same length
    if len(sentence1) != len(sentence2):
        return False
    
    # initialize Union Find structure
    uf = UnionFind()
    
    # union all similar pairs
    for word1, word2 in similarPairs:
        uf.union(word1, word2)
    
    # check corresponding words in both sentences
    for w1, w2 in zip(sentence1, sentence2):
        # words are similar if they are the same 
        # or if they have same root in union find
        if w1 == w2:
            continue
        if uf.find(w1) != uf.find(w2):
            return False
    return True

# Example usage:
sentence1 = ["great","acting","skills"]
sentence2 = ["fine","drama","talent"]
similarPairs = [["great","good"],["fine","good"],["drama","acting"],["skills","talent"]]
print(areSentencesSimilarTwo(sentence1, sentence2, similarPairs))  # Expected output: True