# 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:
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.



# 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

• public class Synonymous_Sentences {

class Solution {

// word => its similar words set
Map<String, Set<String>> map = new HashMap<>();
List<String> res = new ArrayList<>();

public List<String> generateSentences(List<List<String>> synonyms, String text) {

//build graph.
for (List<String> s : synonyms) {
String a = s.get(0);
String b = s.get(1);
}

String[] split = text.split("\\W+");
helper(split, 0, "");

Collections.sort(res);
return res;
}

public void helper(String[] wordsArray, int index, String cur) {

if (index == wordsArray.length) {
return;
}

if (map.containsKey(wordsArray[index])) {
List<String> choices = new ArrayList<>();
//find all synonyms related to s
getSynonyms(wordsArray[index], new HashSet<>(), choices);

//try to change word at index to every possible synonyms word
for (String s : choices) {
helper(wordsArray, index + 1, cur + (index == wordsArray.length - 1 ? s : s + " "));
}
} else {
//if the word at index has no synonyms, just go for next.
helper(wordsArray, index + 1, cur + (index == wordsArray.length - 1 ? wordsArray[index] : wordsArray[index] + " "));
}
}

//get all synonyms related to s
public void getSynonyms(String s, Set<String> visited, List<String> choices) {
for (String each : map.get(s)) {
if (!visited.contains(each)) {
getSynonyms(each, visited, choices);
}
}
}
}
}


• // OJ: https://leetcode.com/problems/synonymous-sentences/
// Time: O(NlogN)
// Space: O(N)
class UnionFind {
vector<int> id;
public:
UnionFind(int N) : id(N) {
iota(begin(id), end(id), 0);
}
int find(int a) {
return id[a] == a ? a : (id[a] = find(id[a]));
}
void connect(int a, int b) {
id[find(a)] = find(b);
}
};
class Solution {
public:
vector<string> generateSentences(vector<vector<string>>& A, string s) {
istringstream ss(s);
string word;
vector<string> v, tmp, ans;
while (ss >> word) v.push_back(word);
int id = 0;
unordered_map<string, int> index;
unordered_map<int, string> rindex;
for (auto &syn : A) {
if (index.count(syn) == 0) {
index[syn] = id;
rindex[id] = syn;
++id;
}
if (index.count(syn) == 0) {
index[syn] = id;
rindex[id] = syn;
++id;
}
}
UnionFind uf(index.size());
for (auto &syn : A) {
uf.connect(index[syn], index[syn]);
}
unordered_map<int, set<string>> m;
for (int i = 0; i < index.size(); ++i) {
m[uf.find(i)].insert(rindex[i]);
}
function<void(int)> dfs = [&](int i) {
if (i == v.size()) {
string t;
for (auto &w : tmp) {
if (t.size()) t += ' ';
t += w;
}
ans.push_back(t);
return;
}
if (index.count(v[i])) {
for (auto &syn : m[uf.find(index[v[i]])]) {
tmp.push_back(syn);
dfs(i + 1);
tmp.pop_back();
}
} else {
tmp.push_back(v[i]);
dfs(i + 1);
tmp.pop_back();
}
};
dfs(0);
return ans;
}
};

• class Solution:
def generateSentences(self, synonyms: List[List[str]], text: str) -> List[str]:
p = {}

def find(x):
if p[x] != x:
p[x] = find(p[x])
return p[x]

for a, b in synonyms:
p[a] = a
p[b] = b
for a, b in synonyms:
p[find(a)] = find(b)

s = defaultdict(set)
for a, b in synonyms:
res = []
for word in text.split(' '):
if word not in p:
if not res:
res.append([word])
else:
for a in res:
a.append(word)
else:
words = sorted(s[find(word)])
if not res:
for b in words:
res.append([b])
else:
res = [a + [b] for a in res for b in words]
return [' '.join(sentence) for sentence in res]