737. Sentence Similarity II

Problem Description

The problem provides us with two sentences, each represented as an array of words, and an array of word pairs called similarPairs. Each pair consists of words that are considered similar to each other. The task is to determine if the two sentences are similar by adhering to two conditions:

1. Both sentences must be of the same length, meaning they should contain the same number of words.
2. For each corresponding pair of words from sentence1 and sentence2, the words must be similar. It's given that the similarity relationship is transitive. That means if a is similar to b and b is similar to c, then a is similar to c.

A word is always similar to itself. The output should be true if the sentences are similar, otherwise false.

Intuition

To solve this problem, we need to figure out a way to keep track of which words are similar to each other. This requires not just checking direct similarities, but also indirect (transitive) connections between words.

The intuition behind the solution is to use Union-Find, a data structure that efficiently handles the equivalence relations, which is precisely what we need to determine the similarity between words. The core idea of Union-Find is to group similar words together so that we can quickly find out if two words are in the same group.

Here is how we approach the solution:

• First, we need to check if both sentences are of the same length. If not, we can immediately return false.
• Then, we initialize Union-Find. For that purpose, we use a list called p, which will serve as the parent pointer for each element. At the start, each element is its own parent, indicating different sets. To efficiently track the indices for each word, a dictionary named words maps each word to a unique index.
• We iterate through each pair in similarPairs and perform the union operation, merging the sets that contain the two words in each pair.
• Next, we compare words in the same positions from both sentences. If they are the same, we move on to the next pair. If not, we check if they are indirectly similar through the Union-Find data structure by finding their root parents and comparing them. If they have different root parents, we conclude the sentences are not similar and return false.
• If none of the above returns false, it means all words are sufficiently similar, and we return true.

By using Union-Find, we can handle the transitivity of similarity and quickly query any two words to see if they are part of the same group, thus determining if the sentences are similar or not.

Learn more about Depth-First Search, Breadth-First Search and Union Find patterns.

Solution Approach

The solution to this problem uses the Union-Find algorithm. Let's break down how the code implements this algorithm and how it applies to the problem.

• Initially, a p list is created, using list comprehension, with n << 1 elements where n is the number of pairs in similarPairs. The expression n << 1 is equivalent to multiplying n by 2 since it shifts the bits of n to the left by one, effectively doubling the number. This creates a list with indices from 0 to 2n - 1, and each element is initialized to its own index, representing the initial parent of itself.

• The find function is a recursive function that takes an index x and finds the root parent of x. It does so by checking if p[x] is not equal to x, which means x is not its own parent and it must have a parent somewhere up in its ancestor chain. The function continues to call itself with the parent of x until it reaches the root parent. To optimize this process for future lookups, path compression is used by setting p[x] to the root parent found. This means the next time we call find on x, it will directly reference its root parent.

• The words dictionary is used to assign each unique word a unique index. When we encounter a new word in similarPairs, we assign it the next available index in the sequence.

• To merge two word sets, the union operation is performed by setting the parent of one representative (found by find) to be the representative of the other. This effectively merges the sets, making them part of a single group.

• The main logic iterates through each pair of words in sentence1 and sentence2. If the current words are the same, they are trivially similar, and the algorithm moves on to the next pair. Otherwise, if one of the words is not in the words dictionary or if the root parents of the two words differ (found via find), the sentences are not similar, and the algorithm returns false.

If all word pairs are found to be similar, the algorithm returns true after iterating through all word pairs. This means that all pairs have the same root parent (are in the same set), satisfying the similarity condition according to the transitivity property of the given relationship.

By using a combination of Union-Find with path compression and an efficient mapping of words to indices, the solution effectively checks the similarity of the sentences in relatively quick operations for each word pair.

In summary, the solution approach employs the Union-Find algorithm with path compression to determine if two sentences represented by arrays of words are similar based on the similarity of word pairs provided.

Example Walkthrough

Let's consider an example to illustrate how the Union-Find algorithm is applied to determine if two sentences are similar.

Suppose we have the following inputs:

• sentence1 = ["great", "acting", "skills"]
• sentence2 = ["fine", "drama", "talent"]
• similarPairs = [("great", "good"), ("good", "fine"), ("acting", "drama"), ("skills", "talent")]

1. Check Length: First, we verify that both sentences are the same length. Here, both have three words, so we can proceed.

2. Initialize Union-Find: We initialize p with indices up to 2n - 1, where n is the number of unique words across all similarPairs. In this case, n = 6 (since "great", "good", "fine", "acting", "drama", and "skills" are all unique), so p = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11].

3. Map Words to Indices: We create a words dictionary where each word is mapped to a unique index. It would look like this after processing all similarPairs:

   1{
   2    "great": 0,
   3    "good": 1,
   4    "fine": 2,
   5    "acting": 3,
   6    "drama": 4,
   7    "skills": 5,
   8    "talent": 6
   9}

4. Union operation: We iterate through similarPairs and perform union operations using the indices from words dictionary. After performing unions, the representative parents might look like this:

   1// "good" and "great" are similar.
   2p[find(1)] = find(0) // p[1] = 0
   3
   4// "good" and "fine" are similar, and "good" is linked to "great", so indirectly "fine" is linked to "great".
   5p[find(2)] = find(1) // p[2] = 0
   6
   7// "acting" and "drama" are similar.
   8p[find(4)] = find(3) // p[4] = 3
   9
   10// "skills" and "talent" are similar.
   11p[find(6)] = find(5) // p[6] = 5

5. Comparing Sentences: Finally, we compare sentence1 and sentence2 word by word.

   • For "great" and "fine", look up each word in the words dictionary, get their indices, and use the find function to check if they have the same parent. Since "fine" has been indirectly linked to "great", they have the same parent.
   • For "acting" and "drama", do the same, and it will reveal that they have the same parent because they have been directly linked.
   • For "skills" and "talent", they have also been directly linked, so they share the same parent.

   Since for all pairs of words, either they are the same word or they belong to the same set (have the same representative parent in Union-Find terminologies), the algorithm will return true.

   The execution concludes that sentence1 and sentence2 are indeed similar.

Solution Implementation

Time and Space Complexity

Time Complexity

The time complexity of the provided code is analyzed as follows:

1. Initializing the parent array p with n << 1 elements takes O(2n) time where n is the number of similar pairs. Since each pair provides two elements, we have a maximum of 2n unique words.
2. The find function is a path compression optimized union-find operation. This results in an amortized time complexity of O(α(n)) per find operation, where α is the inverse Ackermann function, which is a very slow-growing function and can be considered almost constant for all practical purposes.
3. Building the words dictionary for all unique words in similarPairs takes O(n) operations, as we're doing constant time insertions.
4. The union operations in the loop for creating the words dictionary will run n times which will have a complexity of O(nα(n)), since each union (by the find operation) has a complexity of O(α(n)).
5. The for loop to compare actual sentences runs len(sentence1) times. In the worst case, each look-up and each find operation is O(α(n)). Since there are two find operations for each word-pair comparison, the total time complexity for this part is O(2mα(n)), where m is the number of words in sentence1/sentence2.

Therefore, the overall time complexity of the code is:

O(2n) + O(n) + O(nα(n)) + O(2mα(n))

Simplifying, since α(n) is a very slow-growing function and can be treated as almost constant:

O(2n + n + n + 2m)

O(4n + 2m)

The time complexity is essentially linear with respect to the total number of elements in similarPairs and the length of the sentence1 and sentence2. When assuming α(n) is constant, this can be simplified further to:

O(n + m)

Space Complexity

For space complexity, the following is taken into consideration:

1. The parent array p has a size of 2n, which is O(2n).
2. The words dictionary storage depends on the number of unique words across similarPairs, so in the worst case if all words are unique, it will be O(2n).
3. The find function uses recursive stack space, but due to path compression, the depth will be very shallow on average, contributing insignificantly to the overall space complexity.

Hence, the overall space complexity of the program is:

O(2n) + O(2n)

Which simplifies to:

O(4n)

Considering just the unique elements count, this is:

O(n)

The space complexity is linear with respect to the number of unique elements present in similarPairs.

Learn more about how to find time and space complexity quickly using problem constraints.