Synonymous Sentences

You are given a sentence and a list of synonymous words, and you have to generate all possible synonymous sentences by replacing words in the original sentence with their synonyms.

Here’s a step-by-step solution to the problem:

  1. Create a Synonym Mapping: Build a mapping of synonymous words by connecting words that are equivalent. You can use a Union-Find (Disjoint-Set) structure or just a graph to connect synonymous words.

  2. Create Synonym Groups: Use Depth-First Search (DFS) or Union-Find to create a set of synonymous words for each unique word in the synonyms list.

  3. Split the Text: Break the given text into words.

  4. Generate Sentences: Recursively generate all possible sentences by replacing words in the original sentence with their synonymous words. Utilize the synonym groups created in step 2.

  5. Sort the Sentences: Sort the generated sentences lexicographically.

Below is the code implementing these steps:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

from collections import defaultdict

class Solution:
    def generateSentences(self, synonyms: List[List[str]], text: str) -> List[str]:
        graph = defaultdict(list)
        for s1, s2 in synonyms:
            graph[s1].append(s2)
            graph[s2].append(s1)

        # Function to get all synonymous words for a given word
        def get_synonyms(word):
            synonyms = set()
            visited = set()
            stack = [word]
            while stack:
                current_word = stack.pop()
                if current_word not in visited:
                    visited.add(current_word)
                    synonyms.add(current_word)
                    stack.extend(graph[current_word])
            return sorted(list(synonyms))

        # Recursive function to generate sentences
        def generate_sentences(words, current):
            if not words:
                sentences.append(" ".join(current))
                return
            word = words[0]
            synonymous_words = get_synonyms(word)
            for synonym in synonymous_words:
                generate_sentences(words[1:], current + [synonym])

        words = text.split()
        sentences = []
        generate_sentences(words, [])

        return sorted(sentences)

Given the constraints, this code will run efficiently and provide all possible synonymous sentences sorted lexicographically.