1/**
2 * Union-Find (Disjoint Set Union) data structure with path compression and union by size
3 */
4class UnionFind {
5    private int[] parent;  // parent[i] stores the parent of node i
6    private int[] size;    // size[i] stores the size of the tree rooted at i
7  
8    /**
9     * Initialize Union-Find structure with n elements (0 to n-1)
10     * @param n number of elements
11     */
12    public UnionFind(int n) {
13        parent = new int[n];
14        size = new int[n];
15        for (int i = 0; i < n; i++) {
16            parent[i] = i;  // Initially, each element is its own parent
17            size[i] = 1;    // Initially, each tree has size 1
18        }
19    }
20  
21    /**
22     * Find the root of the set containing element x with path compression
23     * @param x the element to find
24     * @return the root of the set containing x
25     */
26    public int find(int x) {
27        if (parent[x] != x) {
28            parent[x] = find(parent[x]);  // Path compression: make x point directly to root
29        }
30        return parent[x];
31    }
32  
33    /**
34     * Union two sets containing elements a and b using union by size
35     * @param a first element
36     * @param b second element
37     */
38    public void union(int a, int b) {
39        int rootA = find(a);
40        int rootB = find(b);
41      
42        if (rootA != rootB) {
43            // Union by size: attach smaller tree to larger tree
44            if (size[rootA] > size[rootB]) {
45                parent[rootB] = rootA;
46                size[rootA] += size[rootB];
47            } else {
48                parent[rootA] = rootB;
49                size[rootB] += size[rootA];
50            }
51        }
52    }
53}
54
55/**
56 * Solution for generating all possible sentences using synonyms
57 */
58class Solution {
59    private List<String> allSentences;           // Store all generated sentences
60    private List<String> currentSentence;        // Current sentence being built
61    private List<String> wordsList;              // List of all unique words from synonyms
62    private Map<String, Integer> wordToIndex;    // Map word to its index in wordsList
63    private UnionFind unionFind;                 // Union-Find to group synonyms
64    private List<Integer>[] synonymGroups;       // synonymGroups[i] contains indices of words in group i
65    private String[] originalWords;              // Words from the original sentence
66  
67    /**
68     * Generate all possible sentences by replacing words with their synonyms
69     * @param synonyms list of synonym pairs
70     * @param text the original sentence
71     * @return list of all possible sentences in lexicographical order
72     */
73    public List<String> generateSentences(List<List<String>> synonyms, String text) {
74        // Collect all unique words from synonym pairs
75        Set<String> uniqueWords = new HashSet<>();
76        for (List<String> pair : synonyms) {
77            uniqueWords.addAll(pair);
78        }
79      
80        // Convert set to list and create word-to-index mapping
81        wordsList = new ArrayList<>(uniqueWords);
82        int n = wordsList.size();
83        wordToIndex = new HashMap<>(n);
84        for (int i = 0; i < wordsList.size(); i++) {
85            wordToIndex.put(wordsList.get(i), i);
86        }
87      
88        // Build Union-Find structure to group synonyms
89        unionFind = new UnionFind(n);
90        for (List<String> pair : synonyms) {
91            unionFind.union(wordToIndex.get(pair.get(0)), wordToIndex.get(pair.get(1)));
92        }
93      
94        // Group words by their root in Union-Find
95        synonymGroups = new List[n];
96        Arrays.setAll(synonymGroups, k -> new ArrayList<>());
97        for (int i = 0; i < n; i++) {
98            synonymGroups[unionFind.find(i)].add(i);
99        }
100      
101        // Sort each group lexicographically
102        for (List<Integer> group : synonymGroups) {
103            group.sort((i, j) -> wordsList.get(i).compareTo(wordsList.get(j)));
104        }
105      
106        // Initialize for DFS
107        originalWords = text.split(" ");
108        allSentences = new ArrayList<>();
109        currentSentence = new ArrayList<>();
110      
111        // Start DFS to generate all sentences
112        dfs(0);
113      
114        return allSentences;
115    }
116  
117    /**
118     * DFS to generate all possible sentences
119     * @param wordIndex current position in the original sentence
120     */
121    private void dfs(int wordIndex) {
122        // Base case: reached end of sentence
123        if (wordIndex >= originalWords.length) {
124            allSentences.add(String.join(" ", currentSentence));
125            return;
126        }
127      
128        String currentWord = originalWords[wordIndex];
129      
130        // If current word has no synonyms, use it as is
131        if (!wordToIndex.containsKey(currentWord)) {
132            currentSentence.add(currentWord);
133            dfs(wordIndex + 1);
134            currentSentence.remove(currentSentence.size() - 1);
135        } else {
136            // Try all synonyms of the current word (including itself)
137            int rootIndex = unionFind.find(wordToIndex.get(currentWord));
138            for (int synonymIndex : synonymGroups[rootIndex]) {
139                currentSentence.add(wordsList.get(synonymIndex));
140                dfs(wordIndex + 1);
141                currentSentence.remove(currentSentence.size() - 1);
142            }
143        }
144    }
145}
146

1class UnionFind {
2public:
3    // Constructor: Initialize Union-Find with n elements
4    UnionFind(int n) {
5        parent = vector<int>(n);
6        rank = vector<int>(n, 1);
7        // Initially, each element is its own parent
8        iota(parent.begin(), parent.end(), 0);
9    }
10
11    // Unite two sets containing elements a and b
12    void unite(int a, int b) {
13        int rootA = find(a);
14        int rootB = find(b);
15      
16        if (rootA != rootB) {
17            // Union by rank: attach smaller tree under larger tree
18            if (rank[rootA] > rank[rootB]) {
19                parent[rootB] = rootA;
20                rank[rootA] += rank[rootB];
21            } else {
22                parent[rootA] = rootB;
23                rank[rootB] += rank[rootA];
24            }
25        }
26    }
27
28    // Find the root of element x with path compression
29    int find(int x) {
30        if (parent[x] != x) {
31            parent[x] = find(parent[x]);  // Path compression
32        }
33        return parent[x];
34    }
35
36private:
37    vector<int> parent;  // Parent array for Union-Find
38    vector<int> rank;    // Rank/size array for union by rank
39};
40
41class Solution {
42public:
43    vector<string> generateSentences(vector<vector<string>>& synonyms, string text) {
44        // Step 1: Collect all unique words from synonym pairs
45        unordered_set<string> uniqueWords;
46        for (auto& pair : synonyms) {
47            uniqueWords.insert(pair[0]);
48            uniqueWords.insert(pair[1]);
49        }
50      
51        // Convert set to vector for indexing
52        vector<string> wordList(uniqueWords.begin(), uniqueWords.end());
53      
54        // Step 2: Create word-to-index mapping
55        unordered_map<string, int> wordToIndex;
56        int numWords = wordList.size();
57        for (int i = 0; i < numWords; ++i) {
58            wordToIndex[wordList[i]] = i;
59        }
60      
61        // Step 3: Build Union-Find structure for synonym groups
62        UnionFind uf(numWords);
63        for (auto& pair : synonyms) {
64            uf.unite(wordToIndex[pair[0]], wordToIndex[pair[1]]);
65        }
66      
67        // Step 4: Group words by their root (synonym groups)
68        vector<vector<int>> synonymGroups(numWords);
69        for (int i = 0; i < numWords; ++i) {
70            synonymGroups[uf.find(i)].push_back(i);
71        }
72      
73        // Sort each synonym group lexicographically
74        for (int i = 0; i < numWords; ++i) {
75            sort(synonymGroups[i].begin(), synonymGroups[i].end(), 
76                 [&](int a, int b) {
77                     return wordList[a] < wordList[b];
78                 });
79        }
80      
81        // Step 5: Parse input text into words
82        vector<string> sentenceWords;
83        string word;
84        istringstream stream(text);
85        while (stream >> word) {
86            sentenceWords.push_back(word);
87        }
88      
89        // Step 6: Generate all possible sentences using DFS
90        vector<string> result;
91        vector<string> currentSentence;
92      
93        function<void(int)> generateCombinations = [&](int wordIndex) {
94            // Base case: reached end of sentence
95            if (wordIndex >= sentenceWords.size()) {
96                // Build sentence string from current combination
97                string sentence;
98                for (int j = 0; j < currentSentence.size(); ++j) {
99                    if (j > 0) {
100                        sentence += " ";
101                    }
102                    sentence += currentSentence[j];
103                }
104                result.push_back(sentence);
105                return;
106            }
107          
108            // Check if current word has synonyms
109            if (wordToIndex.find(sentenceWords[wordIndex]) == wordToIndex.end()) {
110                // Word has no synonyms, use it as-is
111                currentSentence.push_back(sentenceWords[wordIndex]);
112                generateCombinations(wordIndex + 1);
113                currentSentence.pop_back();
114            } else {
115                // Word has synonyms, try all synonyms in the group
116                int wordIdx = wordToIndex[sentenceWords[wordIndex]];
117                int rootIdx = uf.find(wordIdx);
118              
119                for (int synonymIdx : synonymGroups[rootIdx]) {
120                    currentSentence.push_back(wordList[synonymIdx]);
121                    generateCombinations(wordIndex + 1);
122                    currentSentence.pop_back();
123                }
124            }
125        };
126      
127        generateCombinations(0);
128        return result;
129    }
130};
131

1// Parent array for Union-Find structure
2let parent: number[];
3// Rank/size array for union by rank optimization
4let rank: number[];
5
6/**
7 * Initialize Union-Find data structure with n elements
8 * @param n - Number of elements to initialize
9 */
10function initializeUnionFind(n: number): void {
11    parent = new Array(n);
12    rank = new Array(n).fill(1);
13    // Initially, each element is its own parent
14    for (let i = 0; i < n; i++) {
15        parent[i] = i;
16    }
17}
18
19/**
20 * Find the root of element x with path compression
21 * @param x - Element to find root for
22 * @returns Root element of x's set
23 */
24function find(x: number): number {
25    if (parent[x] !== x) {
26        // Path compression: make every node point directly to root
27        parent[x] = find(parent[x]);
28    }
29    return parent[x];
30}
31
32/**
33 * Unite two sets containing elements a and b
34 * @param a - First element
35 * @param b - Second element
36 */
37function unite(a: number, b: number): void {
38    const rootA = find(a);
39    const rootB = find(b);
40  
41    if (rootA !== rootB) {
42        // Union by rank: attach smaller tree under larger tree
43        if (rank[rootA] > rank[rootB]) {
44            parent[rootB] = rootA;
45            rank[rootA] += rank[rootB];
46        } else {
47            parent[rootA] = rootB;
48            rank[rootB] += rank[rootA];
49        }
50    }
51}
52
53/**
54 * Generate all possible sentences by replacing words with their synonyms
55 * @param synonyms - Array of synonym pairs
56 * @param text - Input sentence as string
57 * @returns Array of all possible sentences sorted lexicographically
58 */
59function generateSentences(synonyms: string[][], text: string): string[] {
60    // Step 1: Collect all unique words from synonym pairs
61    const uniqueWords = new Set<string>();
62    for (const pair of synonyms) {
63        uniqueWords.add(pair[0]);
64        uniqueWords.add(pair[1]);
65    }
66  
67    // Convert set to array for indexing
68    const wordList = Array.from(uniqueWords);
69  
70    // Step 2: Create word-to-index mapping
71    const wordToIndex = new Map<string, number>();
72    const numWords = wordList.length;
73    for (let i = 0; i < numWords; i++) {
74        wordToIndex.set(wordList[i], i);
75    }
76  
77    // Step 3: Build Union-Find structure for synonym groups
78    initializeUnionFind(numWords);
79    for (const pair of synonyms) {
80        unite(wordToIndex.get(pair[0])!, wordToIndex.get(pair[1])!);
81    }
82  
83    // Step 4: Group words by their root (synonym groups)
84    const synonymGroups: number[][] = Array.from({ length: numWords }, () => []);
85    for (let i = 0; i < numWords; i++) {
86        synonymGroups[find(i)].push(i);
87    }
88  
89    // Sort each synonym group lexicographically
90    for (let i = 0; i < numWords; i++) {
91        synonymGroups[i].sort((a, b) => {
92            return wordList[a].localeCompare(wordList[b]);
93        });
94    }
95  
96    // Step 5: Parse input text into words
97    const sentenceWords = text.split(' ');
98  
99    // Step 6: Generate all possible sentences using DFS
100    const result: string[] = [];
101    const currentSentence: string[] = [];
102  
103    /**
104     * Recursively generate all combinations of sentences
105     * @param wordIndex - Current position in sentence being processed
106     */
107    function generateCombinations(wordIndex: number): void {
108        // Base case: reached end of sentence
109        if (wordIndex >= sentenceWords.length) {
110            // Build sentence string from current combination
111            const sentence = currentSentence.join(' ');
112            result.push(sentence);
113            return;
114        }
115      
116        // Check if current word has synonyms
117        if (!wordToIndex.has(sentenceWords[wordIndex])) {
118            // Word has no synonyms, use it as-is
119            currentSentence.push(sentenceWords[wordIndex]);
120            generateCombinations(wordIndex + 1);
121            currentSentence.pop();
122        } else {
123            // Word has synonyms, try all synonyms in the group
124            const wordIdx = wordToIndex.get(sentenceWords[wordIndex])!;
125            const rootIdx = find(wordIdx);
126          
127            for (const synonymIdx of synonymGroups[rootIdx]) {
128                currentSentence.push(wordList[synonymIdx]);
129                generateCombinations(wordIndex + 1);
130                currentSentence.pop();
131            }
132        }
133    }
134  
135    generateCombinations(0);
136    return result;
137}
138