1import java.util.*;
2
3class UnionFind {
4    private int[] parent;     // parent[i] holds the parent of i in the UF structure
5    private int[] size;       // size[i] holds the size of the tree rooted at i
6
7    // Constructor initializes each element's parent to itself and size to 1
8    public UnionFind(int n) {
9        parent = new int[n];
10        size = new int[n];
11        for (int i = 0; i < n; ++i) {
12            parent[i] = i;
13            size[i] = 1;
14        }
15    }
16
17    // find method with path compression, returns the root of the set x belongs to
18    public int find(int x) {
19        if (parent[x] != x) {
20            parent[x] = find(parent[x]);
21        }
22        return parent[x];
23    }
24
25    // Union method to merge sets containing a and b
26    public void union(int a, int b) {
27        int rootA = find(a);
28        int rootB = find(b);
29        if (rootA != rootB) {
30            // Merge smaller tree into the larger one
31            if (size[rootA] > size[rootB]) {
32                parent[rootB] = rootA;
33                size[rootA] += size[rootB];
34            } else {
35                parent[rootA] = rootB;
36                size[rootB] += size[rootA];
37            }
38        }
39    }
40}
41
42class Solution {
43    private List<String> answers = new ArrayList<>();  // List of all possible sentences
44    private List<String> currentSentence = new ArrayList<>();  // Holds the current sentence during DFS
45    private List<String> uniqueWords;  // List of unique words across all synonyms
46    private Map<String, Integer> wordIdMap;  // Maps word to its index
47    private UnionFind unionFind; // Union-Find instance for grouping synonyms
48    private List<Integer>[] synonymGroups;  // Holds groups of synonym indices
49    private String[] originalSentence;  // Original sentence split by whitespace
50
51    // Main method to generate all possible sentences given a list of synonyms and a text string
52    public List<String> generateSentences(List<List<String>> synonyms, String text) {
53        Set<String> setOfSynonyms = new HashSet<>();  // Set to ensure unique words are collected
54        for (List<String> pairs : synonyms) {
55            setOfSynonyms.addAll(pairs);
56        }
57        uniqueWords = new ArrayList<>(setOfSynonyms);
58        int wordCount = uniqueWords.size();
59        wordIdMap = new HashMap<>(wordCount);
60      
61        // Populate the wordIdMap with each unique word's index
62        for (int i = 0; i < uniqueWords.size(); ++i) {
63            wordIdMap.put(uniqueWords.get(i), i);
64        }
65      
66        unionFind = new UnionFind(wordCount);
67        // Perform union operations for all pairs of synonyms
68        for (List<String> pairs : synonyms) {
69            unionFind.union(wordIdMap.get(pairs.get(0)), wordIdMap.get(pairs.get(1)));
70        }
71      
72        // Initialize synonym groups
73        synonymGroups = new List[wordCount];
74        Arrays.setAll(synonymGroups, k -> new ArrayList<>());
75        for (int i = 0; i < wordCount; ++i) {
76            synonymGroups[unionFind.find(i)].add(i);
77        }
78        // Sort groups alphabetically based on the represented words
79        for (List<Integer> group : synonymGroups) {
80            group.sort((i, j) -> uniqueWords.get(i).compareTo(uniqueWords.get(j)));
81        }
82      
83        // Split the original text into words
84        originalSentence = text.split(" ");
85        // Start DFS to build possible sentences
86        dfs(0);
87        return answers;
88    }
89
90    // Helper method to perform DFS and generate all possible sentences
91    private void dfs(int index) {
92        if (index >= originalSentence.length) {
93            answers.add(String.join(" ", currentSentence));
94            return;
95        }
96        // If current word has synonyms
97        if (wordIdMap.containsKey(originalSentence[index])) {
98            // Iterate through all synonyms
99            for (int synonymIndex : synonymGroups[unionFind.find(wordIdMap.get(originalSentence[index]))]) {
100                currentSentence.add(uniqueWords.get(synonymIndex));
101                dfs(index + 1);
102                currentSentence.remove(currentSentence.size() - 1);
103            }
104        } else {
105            // No synonym for current word, add it as is
106            currentSentence.add(originalSentence[index]);
107            dfs(index + 1);
108            currentSentence.remove(currentSentence.size() - 1);
109        }
110    }
111}
112

1#include <vector>
2#include <string>
3#include <unordered_set>
4#include <unordered_map>
5#include <numeric>
6#include <iostream>
7#include <sstream>
8#include <algorithm>
9#include <functional>
10
11using namespace std;
12
13// The UnionFind class is a data structure that provides efficient union and find operations.
14class UnionFind {
15public:
16    // Constructor initializes the union-find structure for n elements.
17    UnionFind(int n) {
18        parent = vector<int>(n);
19        rank = vector<int>(n, 1);
20        iota(parent.begin(), parent.end(), 0); // Fill with consecutive integers.
21    }
22
23    // Unites two subsets into a single subset.
24    void unite(int a, int b) {
25        int parentA = find(a), parentB = find(b);
26        if (parentA != parentB) {
27            // Union by rank heuristic: attach the smaller tree to the root of the larger tree.
28            if (rank[parentA] > rank[parentB]) {
29                parent[parentB] = parentA;
30                rank[parentA] += rank[parentB];
31            } else {
32                parent[parentA] = parentB;
33                rank[parentB] += rank[parentA];
34            }
35        }
36    }
37
38    // Finds the representative of the set that element x is a part of.
39    int find(int x) {
40        if (parent[x] != x) {
41            parent[x] = find(parent[x]); // Path compression heuristic.
42        }
43        return parent[x];
44    }
45
46private:
47    vector<int> parent, rank; // Parent links and ranks of the trees.
48};
49
50class Solution {
51public:
52    // This function generates all possible sentences by substituting synonyms in the given text.
53    vector<string> generateSentences(vector<vector<string>>& synonyms, string text) {
54        unordered_set<string> synonymSet;
55        // Insert all synonyms into a set to remove duplicates.
56        for (auto& pair : synonyms) {
57            synonymSet.insert(pair[0]);
58            synonymSet.insert(pair[1]);
59        }
60      
61        vector<string> words(synonymSet.begin(), synonymSet.end());
62        unordered_map<string, int> wordToId;
63        int n = words.size();
64        // Map each unique word to an ID.
65        for (int i = 0; i < n; ++i) {
66            wordToId[words[i]] = i;
67        }
68      
69        UnionFind unionFind(n);
70        // Unite the synonyms in the Union-Find structure.
71        for (auto& pair : synonyms) {
72            unionFind.unite(wordToId[pair[0]], wordToId[pair[1]]);
73        }
74      
75        vector<vector<int>> groups(n);
76        // Group the synonyms by their root parent.
77        for (int i = 0; i < n; ++i) {
78            groups[unionFind.find(i)].push_back(i);
79        }
80        // Sort each group of synonyms lexicographically.
81        for (int i = 0; i < n; ++i) {
82            sort(groups[i].begin(), groups[i].end(), [&](int a, int b) {
83                return words[a] < words[b];
84            });
85        }
86
87        istringstream iss(text);
88        vector<string> sentenceWords;
89        string currentWord;
90
91        // Split the text into words.
92        while (iss >> currentWord) {
93            sentenceWords.emplace_back(currentWord);
94        }
95
96        vector<string> resultSentences;
97        vector<string> tempSentence;
98
99        // Recursive function to generate all possible sentences.
100        function<void(int)> generate = [&](int i) {
101            if (i >= sentenceWords.size()) {
102                // If at the end of the sentence, join the words and add to the result.
103                string sentence = joinSentence(tempSentence);
104                resultSentences.emplace_back(sentence);
105                return;
106            }
107            if (!wordToId.count(sentenceWords[i])) {
108                // If the word isn't a synonym, add as is.
109                tempSentence.emplace_back(sentenceWords[i]);
110                generate(i + 1);
111                tempSentence.pop_back();
112            } else {
113                // If the word is a synonym, try all possible substitutions.
114                for (int id : groups[unionFind.find(wordToId[sentenceWords[i]])]) {
115                    tempSentence.emplace_back(words[id]);
116                    generate(i + 1);
117                    tempSentence.pop_back();
118                }
119            }
120        };
121
122        generate(0); // Start the recursive generation from the first word.
123        return resultSentences;
124    }
125
126private:
127    // Helper function to join words in a sentence.
128    string joinSentence(const vector<string>& words) {
129        string sentence;
130        for (int i = 0; i < words.size(); ++i) {
131            if (i > 0) {
132                sentence += " ";
133            }
134            sentence += words[i];
135        }
136        return sentence;
137    }
138};
139

1// A global map to keep track of word to ID and ID to word translation.
2const wordToId: Record<string, number> = {};
3const words: string[] = [];
4
5// Union-Find structure to help union and find word groups.
6const parent: number[] = [];
7const rank: number[] = [];
8
9// Helper function to find the representative of the set that element x is a part of.
10function find(x: number): number {
11  if (parent[x] !== x) {
12    parent[x] = find(parent[x]); // Path compression heuristic.
13  }
14  return parent[x];
15}
16
17// Function to unite two subsets into a single subset.
18function unite(a: number, b: number): void {
19  let parentA = find(a);
20  let parentB = find(b);
21  if (parentA !== parentB) {
22    // Union by rank heuristic: attach the smaller tree to the root of the larger tree.
23    if (rank[parentA] > rank[parentB]) {
24      parent[parentB] = parentA;
25      rank[parentA] += rank[parentB];
26    } else {
27      parent[parentA] = parentB;
28      rank[parentB] += rank[parentA];
29    }
30  }
31}
32
33// The main function that generates all possible sentences by substituting synonyms in the given text.
34function generateSentences(synonyms: string[][], text: string): string[] {
35  const synonymSet: Set<string> = new Set();
36
37  // Insert all synonyms into a set to remove duplicates and fill word-related structures.
38  synonyms.flat().forEach((word) => {
39    synonymSet.add(word);
40    if (!wordToId[word]) {
41      wordToId[word] = words.length;
42      words.push(word);
43      const id = words.length - 1;
44      parent[id] = id; // Initially, every word is its own parent.
45      rank[id] = 1; // Initial rank is 1.
46    }
47  });
48
49  // Unite the synonyms in the Union-Find structure.
50  synonyms.forEach(([word1, word2]) => {
51    unite(wordToId[word1], wordToId[word2]);
52  });
53
54  const groups: number[][] = Array.from({ length: words.length }, () => []);
55
56  // Group the synonyms by their root parent.
57  Object.keys(wordToId).forEach((word) => {
58    groups[find(wordToId[word])].push(wordToId[word]);
59  });
60
61  // Sort each group of synonyms lexicographically.
62  groups.forEach((group) => {
63    group.sort((a, b) => words[a].localeCompare(words[b]));
64  });
65
66  const sentenceWords: string[] = text.split(' ');
67  const resultSentences: string[] = [];
68  let tempSentence: string[] = [];
69
70  // Recursive function to generate all possible sentences.
71  const generate = (i: number) => {
72    if (i >= sentenceWords.length) {
73      // If at the end of the sentence, join the words and add to the result.
74      const sentence = tempSentence.join(' ');
75      resultSentences.push(sentence);
76      return;
77    }
78    const currentWord = sentenceWords[i];
79    if (!wordToId[currentWord]) {
80      // If the word isn't a synonym, add as is.
81      tempSentence.push(currentWord);
82      generate(i + 1);
83      tempSentence.pop();
84    } else {
85      // If the word is a synonym, try all possible substitutions.
86      const synonymsGroup = groups[find(wordToId[currentWord])];
87      synonymsGroup.forEach((id) => {
88        tempSentence.push(words[id]);
89        generate(i + 1);
90        tempSentence.pop();
91      });
92    }
93  };
94
95  generate(0); // Start the recursive generation from the first word.
96  return resultSentences;
97}
98