LeetCode Solutions Blog

Synonymous Sentences

Number: 1191

Difficulty: Medium

Paid? Yes

Problem Description

Given a list of equivalent string pairs (synonyms) and a sentence, generate all possible synonymous sentences by replacing words with any of their equivalent synonyms. The final list of sentences must be sorted in lexicographical order.

Key Insights

Use Union Find (or DFS) to group words that are synonyms.
Map each group to its set of equivalent words, then sort each set for lexicographical order.
For every word in the sentence, determine if it belongs to a synonym group. If so, consider all replacements; otherwise, use the word itself.
Use backtracking to generate all possible sentence combinations.
Finally, sort the list of sentences before returning.

Space and Time Complexity

Time Complexity: In the worst-case scenario, every word in the sentence may have up to O(k) synonyms, leading to O(k^w) combinations where w is the number of words. Additionally, union-find operations and sorting have relatively low overhead given the small constraints. Space Complexity: O(N + W) where N is the total number of synonyms and W is the number of words in the sentence, used to store the union-find structure, synonym groups, and the recursion stack.

Solution

We first use a union-find data structure to group synonyms such that any two words in the same group are equivalent. After union-find processing, we create a map from the representative of each group to a sorted list of all words in that group. For each word in the given sentence, if it belongs to a group of synonyms, we substitute it with each possible synonym; if not, it remains unchanged. We use backtracking to generate all possible sentences and then sort them lexicographically before returning.

Code Solutions

# Python solution for generating synonymous sentences

# Union find helper functions
def find(x, parent):
    # Find the root of x with path compression
    if parent[x] != x:
        parent[x] = find(parent[x], parent)
    return parent[x]

def union(x, y, parent):
    # Union two sets by attaching root of one to the other
    rootX = find(x, parent)
    rootY = find(y, parent)
    if rootX != rootY:
        parent[rootY] = rootX

def generateSentences(synonyms, text):
    parent = {}
    
    # Initialize union-find structure for each word in synonyms
    for a, b in synonyms:
        if a not in parent:
            parent[a] = a
        if b not in parent:
            parent[b] = b
        union(a, b, parent)
    
    # Group synonyms by the root found via union-find
    groups = {}
    for word in parent:
        root = find(word, parent)
        if root not in groups:
            groups[root] = set()
        groups[root].add(word)
    
    # Map each word to its sorted synonym list if available
    wordToSynonyms = {}
    for group in groups.values():
        sortedGroup = sorted(list(group))
        for word in group:
            wordToSynonyms[word] = sortedGroup
    
    words = text.split()
    result = []
    
    def backtrack(index, current):
        if index == len(words):
            result.append(" ".join(current))
            return
        word = words[index]
        # If the word has synonyms, try each synonym possibility
        if word in wordToSynonyms:
            for synonym in wordToSynonyms[word]:
                current.append(synonym)
                backtrack(index + 1, current)
                current.pop()
        else:
            # Use the word itself if no synonyms exist
            current.append(word)
            backtrack(index + 1, current)
            current.pop()
    
    backtrack(0, [])
    # Sorting final result lexicographically
    result.sort()
    return result

# Example usage:
synonyms = [["happy","joy"],["sad","sorrow"],["joy","cheerful"]]
text = "I am happy today but was sad yesterday"
print(generateSentences(synonyms, text))