The "Synonymous Sentences" problem asks you to generate all possible sentences by replacing words in a given sentence with their synonyms, as specified by a list of synonym pairs.
Key constraints:
At first glance, you might consider a brute-force approach: for each word in the sentence, replace it with all possible synonyms, and recursively repeat this for each position. However, this quickly becomes inefficient, especially if synonym groups are large or overlap.
The key insight is that synonym relationships are transitive: if "happy" is a synonym of "joyful" and "joyful" of "cheerful", then all three are synonyms. Thus, we need a way to group all connected synonyms together efficiently. This is a classic use-case for the "Union Find" (Disjoint Set Union) data structure.
Once we've grouped synonyms, for each word in the sentence, we can look up its synonym group and generate all possible replacements. Then, we combine all possibilities using backtracking or recursion.
Let's break down the steps to solve the problem efficiently:
We use hash maps for fast lookups, and the union-find structure for efficient group merging and querying.
Example Input:
Synonyms: [["happy", "joy"], ["sad", "sorrow"], ["joy", "cheerful"]]
Sentence: "I am happy today but was sad yesterday"
Brute-force approach:
k synonyms and there are n words, the brute-force approach would generate up to k^n sentences, which is exponential and infeasible for large n or k.O(P) where P is the number of pairs), since union-find with path compression is very fast.O(1) (amortized).O(S), where S is the product of the number of synonyms for each word (i.e., total number of output sentences).O(U + S), where U is the number of unique words in synonym groups, and S is the number of output sentences.The bottleneck is the number of possible sentences, which can still be large if many words have many synonyms, but the algorithm is efficient in all other aspects.
The "Synonymous Sentences" problem is elegantly solved by grouping synonyms using union-find and then generating all possible sentences using backtracking. The main insight is to treat synonym pairs as equivalence classes, allowing us to efficiently look up all synonyms for any word. The final solution is both efficient and clear, leveraging classic data structures and recursive generation techniques to handle all possible combinations.
class Solution:
def generateSentences(self, synonyms, text):
from collections import defaultdict
parent = {}
def find(x):
parent.setdefault(x, x)
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]
def union(x, y):
parent[find(x)] = find(y)
# Build union-find structure
for a, b in synonyms:
union(a, b)
# Build groupings: leader -> set of words
groups = defaultdict(set)
for word in parent:
leader = find(word)
groups[leader].add(word)
# For each word in sentence, get all synonyms (or itself)
words = text.split()
options = []
for w in words:
if w in parent:
leader = find(w)
options.append(sorted(groups[leader]))
else:
options.append([w])
res = []
def backtrack(idx, path):
if idx == len(options):
res.append(' '.join(path))
return
for opt in options[idx]:
backtrack(idx + 1, path + [opt])
backtrack(0, [])
res.sort()
return res
class Solution {
public:
vector<string> generateSentences(vector<vector<string>>& synonyms, string text) {
unordered_map<string, string> parent;
function<string(const string&)> find = [&](const string& x) {
if (!parent.count(x)) parent[x] = x;
if (parent[x] != x) parent[x] = find(parent[x]);
return parent[x];
};
auto unite = [&](const string& a, const string& b) {
parent[find(a)] = find(b);
};
for (auto& pair : synonyms) {
unite(pair[0], pair[1]);
}
unordered_map<string, set<string>> groups;
for (auto& it : parent) {
string leader = find(it.first);
groups[leader].insert(it.first);
}
vector<vector<string>> options;
istringstream iss(text);
string word;
while (iss >> word) {
if (parent.count(word)) {
string leader = find(word);
vector<string> v(groups[leader].begin(), groups[leader].end());
options.push_back(v);
} else {
options.push_back({word});
}
}
vector<string> res;
vector<string> path;
function<void(int)> backtrack = [&](int idx) {
if (idx == options.size()) {
stringstream ss;
for (int i = 0; i < path.size(); ++i) {
if (i) ss << ' ';
ss << path[i];
}
res.push_back(ss.str());
return;
}
for (const string& opt : options[idx]) {
path.push_back(opt);
backtrack(idx + 1);
path.pop_back();
}
};
backtrack(0);
sort(res.begin(), res.end());
return res;
}
};
class Solution {
public List<String> generateSentences(List<List<String>> synonyms, String text) {
Map<String, String> parent = new HashMap<>();
// Union-Find
Function<String, String> find = new Function<>() {
public String apply(String x) {
parent.putIfAbsent(x, x);
if (!parent.get(x).equals(x)) {
parent.put(x, this.apply(parent.get(x)));
}
return parent.get(x);
}
};
// Union
for (List<String> pair : synonyms) {
String a = pair.get(0), b = pair.get(1);
parent.put(find.apply(a), find.apply(b));
}
// Build groupings
Map<String, TreeSet<String>> groups = new HashMap<>();
for (String word : parent.keySet()) {
String leader = find.apply(word);
groups.computeIfAbsent(leader, k -> new TreeSet<>()).add(word);
}
// Process sentence
String[] words = text.split(" ");
List<List<String>> options = new ArrayList<>();
for (String w : words) {
if (parent.containsKey(w)) {
String leader = find.apply(w);
options.add(new ArrayList<>(groups.get(leader)));
} else {
options.add(Arrays.asList(w));
}
}
List<String> res = new ArrayList<>();
backtrack(options, 0, new ArrayList<>(), res);
Collections.sort(res);
return res;
}
private void backtrack(List<List<String>> options, int idx, List<String> path, List<String> res) {
if (idx == options.size()) {
res.add(String.join(" ", path));
return;
}
for (String opt : options.get(idx)) {
path.add(opt);
backtrack(options, idx + 1, path, res);
path.remove(path.size() - 1);
}
}
}
var generateSentences = function(synonyms, text) {
const parent = {};
function find(x) {
if (!(x in parent)) parent[x] = x;
if (parent[x] !== x)
parent[x] = find(parent[x]);
return parent[x];
}
function union(x, y) {
parent[find(x)] = find(y);
}
for (let [a, b] of synonyms) {
union(a, b);
}
const groups = {};
for (let word in parent) {
let leader = find(word);
if (!(leader in groups)) groups[leader] = new Set();
groups[leader].add(word);
}
const words = text.split(' ');
const options = [];
for (let w of words) {
if (w in parent) {
let leader = find(w);
options.push([...groups[leader]].sort());
} else {
options.push([w]);
}
}
const res = [];
function backtrack(idx, path) {
if (idx === options.length) {
res.push(path.join(' '));
return;
}
for (let opt of options[idx]) {
backtrack(idx + 1, path.concat(opt));
}
}
backtrack(0, []);
res.sort();
return res;
};