# Question

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[0] != synonyms[1]
All words consist of at most 10 English letters only.
text is a single space separated sentence of at most 10 words.
```

# Algorithm

Union search, recursive enumeration

`O(2^n⋅L)`

Use the union search to find the synonym group, and then recursively enumerate and replace the synonym.

### Time complexity

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 `O(2^n *L)`

.

### Space complexity

Union search requires O(n) space, and recording answers requires O(2&n *L) space, so the total space complexity is `O(2^n *L)`

.

# Code

Java