Synonymous Sentences - Solution & Explanation

Problem Overview: You are given pairs of synonymous words and a sentence. Replace words with their synonyms to generate every possible sentence variation. The final output must contain all valid sentences sorted lexicographically.

Approach 1: Graph + Backtracking (Time: O(G + S * K^L), Space: O(G + L))

Model synonyms as an undirected graph using a hash table. Each word is a node and each synonym pair forms an edge. Traverse the graph with DFS or BFS to collect all words connected to a given synonym group. While processing the sentence, if a word appears in the graph, replace it with every synonym in its connected component and recursively build sentences using backtracking. This approach directly explores all combinations but repeatedly traverses synonym groups unless cached.

Approach 2: Union-Find + DFS (Time: O(P α(P) + C log C), Space: O(P + C))

Use Union-Find to group synonymous words efficiently. Each pair is unioned so all related words share the same root. After building groups, map each root to a sorted list of synonyms. While constructing sentences, iterate through the input words: if a word belongs to a synonym group, branch into every candidate word from that group and continue recursively using DFS. Sorting each group ensures the final results are generated in lexicographic order without an additional global sort. Union-Find avoids repeated graph traversal and handles large synonym networks efficiently.

Recommended for interviews: Union-Find + DFS is the expected solution. It separates two concerns cleanly: grouping synonyms with Union-Find and generating combinations with DFS. A basic graph + backtracking approach shows you understand the synonym connectivity, but the Union-Find version demonstrates stronger algorithmic design and scales better when the synonym list grows.