Sentence Similarity II

Medium

Asked by:

36 views

Topics:

GraphsArraysStrings

We can represent a sentence as an array of strings, for example, sentence = ["I","am","happy","today"]. Two sentences are similar if we can determine if one sentence can be obtained from another by performing zero or more word replacements.

For example, sentence1 = ["I","am","happy","today"] and sentence2 = ["I","am","sad","today"] are similar if the relationship happy is similar to sad is known.

You are given two sentences sentence1 and sentence2 represented as strings, and a list of similar word pairs pairs, where each pair indicates the two words are similar.

Return true if sentence1 and sentence2 are similar, or false if they are not similar.

Example 1:

Input: sentence1 = ["I","am","happy","today"], sentence2 = ["I","am","happy","today"], pairs = []
Output: true
Explanation: sentence1 and sentence2 are exactly the same, so they are similar.

Example 2:

Input: sentence1 = ["I","am","happy","today"], sentence2 = ["I","am","sad","today"], pairs = [["happy","sad"],["sad","happy"]]
Output: true
Explanation: The words happy and sad are similar.

Example 3:

Input: sentence1 = ["I","am","happy","today"], sentence2 = ["I","am","mad","today"], pairs = [["happy","sad"],["sad","happy"]]
Output: false
Explanation: The words happy and mad are not similar.

Constraints:

1 <= sentence1.length, sentence2.length <= 1000
1 <= sentence1[i].length, sentence2[i].length <= 20
sentence1[i] and sentence2[i] consist of lower-case and upper-case English letters.
0 <= pairs.length <= 2000
0 <= pairs[i].length == 2
1 <= pairs[i][0].length, pairs[i][1].length <= 20
pairs[i][0] and pairs[i][1] consist of lower-case and upper-case English letters.
Each occurrence of a word is unique in both sentences.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum length of the sentences and the number of word pairs in the input?
Are the words in the sentences case-sensitive, or should I treat them as case-insensitive?
If the relationship graph implied by the word pairs contains cycles, should I still consider the sentences similar if the words are reachable through the cycles?
If `word1` and `word2` are the same, are they considered similar?
If no path exists between two words in the sentences, should I return `false` immediately, or consider all pairs?

Brute Force Solution

Approach

The brute force method for checking if two sentences are similar involves checking every possible way words can be related based on the given word pairs. We explore all connections between words to see if a path exists proving the sentences are similar.

Here's how the algorithm would work step-by-step:

First, consider each word in the first sentence and the corresponding word in the second sentence.
For each pair of words, check if they are identical. If they are, move to the next pair of words.
If they are not identical, use the given word pairs to see if there's a direct link showing they are similar. If so, move to the next pair of words.
If there is no direct link, see if there's a chain of links connecting the words, using the given pairs. We check every possible chain of links to see if we can get from the first word to the second.
If after checking all possible chains, the words are still not considered similar, then the sentences are not similar and you can stop.
If you make it through all the pairs of words in the sentences, and all words are either identical or can be linked via the given word pairs, then the sentences are considered similar.

Code Implementation

def are_sentences_similar(sentence1, sentence2, word_pairs):
    if len(sentence1) != len(sentence2):
        return False

    for i in range(len(sentence1)):
        word1 = sentence1[i]
        word2 = sentence2[i]

        if word1 == word2:
            continue

        found = False
        if (word1, word2) in word_pairs or (word2, word1) in word_pairs:
            continue
        
        # Need to explore possible connections between words
        def find_path(start_word, end_word, visited):
            if start_word == end_word:
                return True
            
            visited.add(start_word)
            
            for pair in word_pairs:
                if pair[0] == start_word and pair[1] not in visited:
                    if find_path(pair[1], end_word, visited):
                        return True
                elif pair[1] == start_word and pair[0] not in visited:
                    if find_path(pair[0], end_word, visited):
                        return True
            return False
        
        # Check if there is a chain of links connecting the words
        if not find_path(word1, word2, set()):
            return False
    
    #If all pairs are similar, then return True
    return True

Big(O) Analysis

Time Complexity

O(N * M^2 * L) – The algorithm iterates through each of the N word pairs in the two sentences. For each pair of words, it performs a search (potentially using Depth First Search or Breadth First Search) to determine if a path exists between the two words within the graph represented by the word pairs. In the worst case, the graph might contain M words, and the search could explore all possible paths, leading to O(M^2) complexity for checking similarity between a single word pair since we need to check all possible edges. Thus checking all the pairs could take O(M^2). Also, L is the length of the longest path, and in worst case can become M. Multiplying all factors, the total complexity becomes O(N * M^2 * L).

Space Complexity

O(P) – The algorithm uses a data structure, implicitly a graph or set, to store the word pairs and the connections between them. In the worst-case scenario, all P pairs of words are distinct and need to be stored, where P is the number of word pairs. During the chain checking (likely BFS or DFS), a queue or stack, along with a visited set, may be used, whose size could grow up to the number of distinct words among the word pairs, which is bounded by P. Therefore, the auxiliary space is primarily determined by the storage of these relationships, resulting in a space complexity of O(P).

Optimal Solution

Approach

The efficient approach treats words as connected components in a graph. We determine if two sentences are similar by checking if their corresponding words are connected in the graph, implying a path of similarity exists between them.

Here's how the algorithm would work step-by-step:

Think of each word as a node in a network or web.
If two words are similar (as defined by the given pairs), draw a connection between those two word-nodes.
After mapping all word-pair similarities, build a network of connected words.
Now, for each word in the first sentence, check if a path exists in the network to its corresponding word in the second sentence.
If a path exists for every pair of corresponding words, the sentences are similar. If at least one word-pair has no path, the sentences are dissimilar.
The key is using a quick way to determine if a path exists. An efficient method is to treat each connected component (group of connected words) as a single unit, so words within the same connected component are considered similar.

Code Implementation

def are_sentences_similar_two(sentence1: list[str], sentence2: list[str], similar_pairs: list[list[str]]) -> bool:
    if len(sentence1) != len(sentence2):
        return False

    word_to_component = {}
    component_id = 0

    def find(word):
        if word not in word_to_component:
            word_to_component[word] = word
        if word_to_component[word] != word:
            word_to_component[word] = find(word_to_component[word])
        return word_to_component[word]

    def union(word1, word2):
        root1 = find(word1)
        root2 = find(word2)
        if root1 != root2:
            word_to_component[root1] = root2

    # Build the connected components based on similar pairs
    for word1, word2 in similar_pairs:
        union(word1, word2)

    # Check if corresponding words belong to the same component
    for i in range(len(sentence1)):
        if find(sentence1[i]) != find(sentence2[i]):
            return False

    return True

Big(O) Analysis

Time Complexity

O(N + M*alpha(N) + L) – Building the graph from similar word pairs takes O(M) time, where M is the number of word pairs. Applying a Union-Find algorithm with path compression and union by rank (where alpha(N) is the inverse Ackermann function which grows very slowly and can be considered near constant) to determine connected components across all N unique words takes O(N + M*alpha(N)). Comparing the sentences involves iterating through each of the L words in the sentences, and for each pair, finding their root/connected component takes alpha(N) time or essentially constant. Thus it takes O(L) time. The overall time complexity is O(N + M*alpha(N) + L). If M grows proportionally to N^2 and L grows proportionally to N, this simplifies to O(N^2).

Space Complexity

O(P + V) – The algorithm builds a graph where words are nodes (vertices) and similarity pairs are edges. Let P be the number of word pairs indicating similarity and V be the number of unique words (vertices). The primary auxiliary space comes from storing the graph, often represented using a dictionary or adjacency list, which can take up O(P) space. Additionally, a data structure like a set or dictionary is needed to keep track of connected components during the path finding process, which in the worst case, can take O(V) space where V is the total number of unique words. Therefore, the total auxiliary space is O(P + V).

Edge Cases

Case	How to Handle
sentences1 or sentences2 is null or empty	Return true if both are null or empty; otherwise, return false if only one is null/empty.
words1 or words2 within pairs is null or empty	Treat a null or empty word as unequal to any other word, including other null/empty words.
pairs is null or empty	If pairs is null or empty, return sentences1.equals(sentences2), performing direct string comparison.
sentences1 and sentences2 have different lengths	Return false immediately as sentences of different lengths cannot be similar.
A large number of pairs leading to a large graph	Use an efficient data structure (e.g., HashMap) for graph representation and path finding to avoid exceeding time limits.
Cycles in the pairs relationship	The path finding algorithm (e.g., DFS or BFS) should correctly handle cycles without infinite loops by tracking visited nodes.
pairs contains duplicate relationships	The algorithm should overwrite duplicate pairs, only retaining the last definition of a similarity.
Integer overflow potential with large strings or many pairs	The solution should avoid calculations that could lead to integer overflow or use appropriate data types (e.g., long) if overflow is unavoidable.

sentences1 or sentences2 is null or empty

How to Handle:

Return true if both are null or empty; otherwise, return false if only one is null/empty.

words1 or words2 within pairs is null or empty

How to Handle:

Treat a null or empty word as unequal to any other word, including other null/empty words.

pairs is null or empty

How to Handle:

If pairs is null or empty, return sentences1.equals(sentences2), performing direct string comparison.

sentences1 and sentences2 have different lengths

How to Handle:

Return false immediately as sentences of different lengths cannot be similar.

A large number of pairs leading to a large graph

How to Handle:

Use an efficient data structure (e.g., HashMap) for graph representation and path finding to avoid exceeding time limits.

Cycles in the pairs relationship

How to Handle:

The path finding algorithm (e.g., DFS or BFS) should correctly handle cycles without infinite loops by tracking visited nodes.

pairs contains duplicate relationships

How to Handle:

The algorithm should overwrite duplicate pairs, only retaining the last definition of a similarity.

Integer overflow potential with large strings or many pairs

How to Handle:

The solution should avoid calculations that could lead to integer overflow or use appropriate data types (e.g., long) if overflow is unavoidable.