Synonymous Sentences
Given synonymous word pairs and a sentence, generate all possible sentences by replacing synonyms.
Examples
Input: [[["happy","joy"],["sad","sorrow"],["joy","cheerful"]],"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"]
Input: [[["a","b"]],"a"]
Output: ["a","b"]
Hints
Build a graph of synonym groups using Union-Find.
Replace each word with all possible synonyms in its group.
Generate all combinations using backtracking.
Related Problems
Synonymous Sentences
Given synonymous word pairs and a sentence, generate all possible sentences by replacing synonyms.