Formatted question description: https://leetcode.ca/all/1258.html
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"] Constraints: 0 <= synonyms.length <= 10 synonyms[i].length == 2 synonyms != synonyms All words consist of at most 10 English letters only. text is a single space separated sentence of at most 10 words.
Union search, recursive enumeration
Use the union search to find the synonym group, and then recursively enumerate and replace the synonym.
The total time complexity of finding the synonym group is approximately
O(n), and the time complexity of recursion is
O(2^n *L), where L is the length of the string
O(L) time is required for each word replacement).
Therefore, the total time complexity is
Union search requires O(n) space, and recording answers requires O(2&n *L) space, so the total space complexity is