Sentence Similarity Ii - Leetcode Solution

The Sentence Similarity II problem on LeetCode involves determining whether two sentences are similar or not. The similarity between two sentences is defined by a list of word pairs, where each word pair represents a synonym relationship between two words.

For example, given the following word pairs:

["great", "good"], ["fine", "good"], ["acting","drama"], ["skills","talent"]

The two sentences "I am a good actor" and "I have great talent in drama" would be considered similar, because "great" and "good" are synonyms, and "talent" and "drama" are synonyms as well.

To solve this problem, we can use a union-find data structure to keep track of all the word pairs, and then test each pair of words in the two sentences to see if they are connected by a synonym relationship.

To build the union-find structure, we can iterate over the list of word pairs and add each pair to the structure. Then, for each word in the two sentences that we want to compare, we can find its root node in the union-find structure, and check if the roots of the two words are the same. If they are, then the words are connected by a synonym relationship, and we can continue comparing the remaining words. If not, then the sentences are not similar.

Here is the Python implementation for this solution:

class UnionFind:
    def __init__(self):
        self.parent = {}
    
    def find(self, word):
        if word not in self.parent:
            self.parent[word] = word
            return word
        elif self.parent[word] == word:
            return word
        else:
            root = self.find(self.parent[word])
            self.parent[word] = root
            return root
        
    def union(self, word1, word2):
        root1 = self.find(word1)
        root2 = self.find(word2)
        if root1 != root2:
            self.parent[root1] = root2
    
class Solution:
    def areSentencesSimilarTwo(self, words1: List[str], words2: List[str], pairs: List[List[str]]) -> bool:
        if len(words1) != len(words2):
            return False
        
        uf = UnionFind()
        for pair in pairs:
            uf.union(pair[0], pair[1])
        
        for word1, word2 in zip(words1, words2):
            if word1 != word2 and uf.find(word1) != uf.find(word2):
                return False
        
        return True

The time complexity of this algorithm is O(n + p log p), where n is the total number of words in the two sentences, and p is the number of word pairs in the list. The space complexity is O(p), for storing the parent pointers in the union-find structure.

1