# 1258. Synonymous Sentences

Given a list of pairs of equivalent words synonyms and a sentence text, Return all possible synonymous sentences sorted lexicographically.

Example 1:

Input:
synonyms = [["happy","joy"],["sad","sorrow"],["joy","cheerful"]],
text = "I am happy today but was sad yesterday"
Output:
["I am cheerful today but was sad yesterday",
​​​​​​​"I am cheerful today but was sorrow yesterday",
"I am happy today but was sad yesterday",
"I am happy today but was sorrow yesterday",
"I am joy today but was sad yesterday",
"I am joy today but was sorrow yesterday"]

# Solution

Approach 1: bfs -- deduplication with sets.

Approach 2: union find, then backtracking/recursion.

# Code (Python)

Approach 1:

class Solution:
    def generateSentences(self, synonyms: List[List[str]], text: str) -> List[str]:
        # idea: a graph of several connected subcomponents. Bfs for all substitutions.
        queue = collections.deque([text])
        edges = collections.defaultdict(list)
        for w1, w2 in synonyms:
            edges[w1].append(w2)
            edges[w2].append(w1)
        sentences = set([text])
        
        while queue:
            sentence = queue.popleft()
            splitted = sentence.split(' ')
            for i, word in enumerate(splitted):
                if word in edges:
                    for neighbor in edges[word]:
                        new_sent = ' '.join(splitted[:i] + [neighbor] + splitted[i + 1:])
                        if new_sent not in sentences:
                            sentences.add(new_sent)
                            queue.append(new_sent)
        
        return sorted(list(sentences))

Approach 2:

import collections
import itertools

# can also use the union find data structure
class UnionFind:
    def __init__(self):
        self.unions = {} # item:parent for each item

    def union(self, item1, item2):
        # set item1's parent's immediate parent to item2's parent
        self.unions[self.find(item1)] = self.find(item2)

    def find(self, item):
        # return the parent for the item
        if item not in self.unions:
            self.unions[item] = item
        if self.unions[item] != item: # if here is enough -- no need to while, becase find is recursive
            # path compression: set item's immediate parent to its immediate parent's parent
            self.unions[item] = self.find(self.unions[item])
        return self.unions[item]

class Solution:
    def generateSentences(self, synonyms: List[List[str]], text: str) -> List[str]:
        # idea: use the unionfind data structure
        # group synonyms into unions
        uf = UnionFind()
        for word1, word2 in synonyms:
            uf.union(word1, word2)
        # establish a list of synonyms, head of each group is random
        groups = collections.defaultdict(set)
        for word1, word2 in synonyms:
            groups[uf.find(word1)].add(word1)
            groups[uf.find(word1)].add(word2)
        word_choices = []
        for word in text.split(' '):
            # need to do this check to add words with no synonyms
            if word not in uf.unions: 
                word_choices.append([word])
            else:
                word_choices.append(list(groups[uf.find(word)]))
        return sorted(' '.join(sentence) for sentence in itertools.product(*word_choices))

# Code (C++)

Approach 1:

Approach 2: