Synonymous Sentences
Problem
You are given a list of equivalent string pairs synonyms where synonyms[i] = [a, b] means a and b are synonyms, and a sentence text. Return all possible synonymous sentences sorted lexicographically. Synonymy is transitive: if a~b and b~c then a~c.
synonyms = [["happy","joy"],["sad","sorrow"],["joy","cheerful"]], text = "I am happy today but was sad yesterday"["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"]def generate_sentences(synonyms, text):
parent = {}
def find(x):
parent.setdefault(x, x)
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
for a, b in synonyms: # union all synonym pairs
parent[find(a)] = find(b)
groups = {} # root -> sorted choices
for w in parent:
groups.setdefault(find(w), []).append(w)
for g in groups.values():
g.sort()
words = text.split()
res = []
def dfs(i, cur):
if i == len(words):
res.append(" ".join(cur))
return
w = words[i]
root = parent.get(w)
opts = groups[find(w)] if root is not None else [w]
for choice in opts: # try each synonym, then backtrack
cur.append(choice)
dfs(i + 1, cur)
cur.pop()
dfs(0, [])
return resfunction generateSentences(synonyms, text) {
const parent = new Map();
function find(x) {
if (!parent.has(x)) parent.set(x, x);
while (parent.get(x) !== x) {
parent.set(x, parent.get(parent.get(x)));
x = parent.get(x);
}
return x;
}
for (const [a, b] of synonyms) parent.set(find(a), find(b));
const groups = new Map();
for (const w of parent.keys()) {
const r = find(w);
if (!groups.has(r)) groups.set(r, []);
groups.get(r).push(w);
}
for (const g of groups.values()) g.sort();
const words = text.split(" ");
const res = [];
function dfs(i, cur) {
if (i === words.length) { res.push(cur.join(" ")); return; }
const w = words[i];
const opts = parent.has(w) ? groups.get(find(w)) : [w];
for (const choice of opts) {
cur.push(choice);
dfs(i + 1, cur);
cur.pop();
}
}
dfs(0, []);
return res;
}class Solution {
Map<String, String> parent = new HashMap<>();
String find(String x) {
parent.putIfAbsent(x, x);
while (!parent.get(x).equals(x)) {
parent.put(x, parent.get(parent.get(x)));
x = parent.get(x);
}
return x;
}
public List<String> generateSentences(List<List<String>> synonyms, String text) {
for (List<String> p : synonyms) parent.put(find(p.get(0)), find(p.get(1)));
Map<String, List<String>> groups = new HashMap<>();
for (String w : parent.keySet())
groups.computeIfAbsent(find(w), k -> new ArrayList<>()).add(w);
for (List<String> g : groups.values()) Collections.sort(g);
String[] words = text.split(" ");
List<String> res = new ArrayList<>();
dfs(0, words, new ArrayList<>(), groups, res);
return res;
}
void dfs(int i, String[] words, List<String> cur,
Map<String, List<String>> groups, List<String> res) {
if (i == words.length) { res.add(String.join(" ", cur)); return; }
List<String> opts = parent.containsKey(words[i])
? groups.get(find(words[i])) : List.of(words[i]);
for (String c : opts) {
cur.add(c);
dfs(i + 1, words, cur, groups, res);
cur.remove(cur.size() - 1);
}
}
}class Solution {
unordered_map<string, string> parent;
string find(const string& key) {
if (!parent.count(key)) parent[key] = key;
string x = key;
while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; }
return x;
}
public:
vector<string> generateSentences(vector<vector<string>>& synonyms, string text) {
for (auto& p : synonyms) parent[find(p[0])] = find(p[1]);
unordered_map<string, vector<string>> groups;
for (auto& kv : parent) groups[find(kv.first)].push_back(kv.first);
for (auto& g : groups) sort(g.second.begin(), g.second.end());
vector<string> words, res, cur;
stringstream ss(text); string t;
while (ss >> t) words.push_back(t);
function<void(int)> dfs = [&](int i) {
if (i == (int)words.size()) {
string s; for (int k = 0; k < (int)cur.size(); k++) s += (k ? " " : "") + cur[k];
res.push_back(s); return;
}
vector<string> opts = parent.count(words[i]) ? groups[find(words[i])] : vector<string>{words[i]};
for (auto& c : opts) { cur.push_back(c); dfs(i + 1); cur.pop_back(); }
};
dfs(0);
return res;
}
};Explanation
This problem has two halves: first figure out which words are synonyms of each other, then build every sentence by swapping each word for any word in its synonym group. The clever part is using Union-Find to handle the "transitive" rule (if a~b and b~c, then a~c).
Union-Find keeps a parent map where each word points toward a representative ("root") of its group. The find helper follows those pointers up to the root, and for every synonym pair we union them by pointing one root at the other. After processing all pairs, words in the same group all share the same root.
We then bucket words by their root into groups and sort each bucket so the output comes out in lexicographic order. Each word now maps to a sorted list of choices.
The second half is plain backtracking. The dfs(i, cur) function walks word position i: it tries every choice for that word, recurses to the next position, then pops the choice (undoes it) before trying the next. When i reaches the end, it joins cur into a finished sentence.
Example: with happy/joy/cheerful as one group (3 choices) and sad/sorrow as another (2 choices), the sentence "I am happy ... was sad ..." produces 3 × 2 = 6 sentences, each emitted in sorted word order.