Synonymous Sentences

Problem

You are given a list of equivalent string pairs synonyms where synonyms[i] = [si, ti] indicates that si and ti are equivalent strings. You are also given a sentence text.

Return all possible synonymous sentencessorted lexicographically.

Examples

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"]

Example 2:

Input: synonyms = [["happy","joy"],["cheerful","glad"]], text = "I am happy today but was sad yesterday"
Output: ["I am happy today but was sad yesterday","I am joy today but was sad yesterday"]

Constraints:

• 0 <= synonyms.length <= 10
• synonyms[i].length == 2
• 1 <= si.length, ti.length <= 10
• si != ti
• text consists of at most 10 words.
• All the pairs of synonyms are unique.
• The words of text are separated by single spaces.

Solution

Approach

We use union-find to group all synonyms into equivalence classes. For each word in the sentence, we collect all possible synonyms (including itself) from its group. Then, we use backtracking to generate all possible sentences and return them sorted lexicographically.

---

Code

C++

#include <vector>
#include <string>
#include <unordered_map>
#include <set>
#include <algorithm>
using namespace std;
class Solution {
    unordered_map<string, string> parent;
    string find(string x) {
        if (parent.count(x) == 0) parent[x] = x;
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[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, set<string>> groups;
        for (auto& p : synonyms) {
            string g = find(p[0]);
            groups[g].insert(p[0]);
            groups[g].insert(p[1]);
        }
        vector<string> words;
        string w;
        for (char c : text) {
            if (c == ' ') { words.push_back(w); w.clear(); }
            else w += c;
        }
        if (!w.empty()) words.push_back(w);
        vector<vector<string>> options;
        for (auto& word : words) {
            string g = find(word);
            if (groups.count(g)) {
                vector<string> v(groups[g].begin(), groups[g].end());
                sort(v.begin(), v.end());
                options.push_back(v);
            } else {
                options.push_back({word});
            }
        }
        vector<string> res;
        function<void(int, string)> dfs = [&](int i, string s) {
            if (i == options.size()) { res.push_back(s.substr(1)); return; }
            for (auto& w : options[i]) dfs(i+1, s + " " + w);
        };
        dfs(0, "");
        sort(res.begin(), res.end());
        return res;
    }
};

Java

import java.util.*;
class Solution {
    Map<String, String> parent = new HashMap<>();
    String find(String x) {
        if (!parent.containsKey(x)) parent.put(x, x);
        if (!parent.get(x).equals(x)) parent.put(x, find(parent.get(x)));
        return parent.get(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, Set<String>> groups = new HashMap<>();
        for (List<String> p : synonyms) {
            String g = find(p.get(0));
            groups.computeIfAbsent(g, k -> new TreeSet<>()).add(p.get(0));
            groups.get(g).add(p.get(1));
        }
        String[] words = text.split(" ");
        List<List<String>> options = new ArrayList<>();
        for (String word : words) {
            String g = find(word);
            if (groups.containsKey(g)) {
                List<String> v = new ArrayList<>(groups.get(g));
                Collections.sort(v);
                options.add(v);
            } else {
                options.add(Arrays.asList(word));
            }
        }
        List<String> res = new ArrayList<>();
        dfs(options, 0, new StringBuilder(), res);
        Collections.sort(res);
        return res;
    }
    void dfs(List<List<String>> options, int i, StringBuilder sb, List<String> res) {
        if (i == options.size()) {
            res.add(sb.toString().trim());
            return;
        }
        for (String w : options.get(i)) {
            int len = sb.length();
            sb.append(" ").append(w);
            dfs(options, i+1, sb, res);
            sb.setLength(len);
        }
    }
}

Kotlin

class Solution {
    fun generateSentences(synonyms: List<List<String>>, text: String): List<String> {
        val parent = mutableMapOf<String, String>()
        fun find(x: String): String {
            if (parent[x] == null) parent[x] = x
            if (parent[x] != x) parent[x] = find(parent[x]!!)
            return parent[x]!!
        }
        for (p in synonyms) parent[find(p[0])] = find(p[1])
        val groups = mutableMapOf<String, MutableSet<String>>()
        for (p in synonyms) {
            val g = find(p[0])
            groups.getOrPut(g) { sortedSetOf() }.add(p[0])
            groups[g]!!.add(p[1])
        }
        val words = text.split(" ")
        val options = words.map { word ->
            val g = find(word)
            if (groups.containsKey(g)) groups[g]!!.toList().sorted() else listOf(word)
        }
        val res = mutableListOf<String>()
        fun dfs(i: Int, sb: StringBuilder) {
            if (i == options.size) {
                res.add(sb.toString().trim())
                return
            }
            for (w in options[i]) {
                val len = sb.length
                sb.append(" ").append(w)
                dfs(i+1, sb)
                sb.setLength(len)
            }
        }
        dfs(0, StringBuilder())
        return res.sorted()
    }
}

Python

from collections import defaultdict
class Solution:
    def generateSentences(self, synonyms: list[list[str]], text: str) -> list[str]:
        parent = {}
        def find(x):
            if x not in parent: parent[x] = x
            if parent[x] != x: parent[x] = find(parent[x])
            return parent[x]
        for a, b in synonyms:
            parent[find(a)] = find(b)
        groups = defaultdict(set)
        for a, b in synonyms:
            g = find(a)
            groups[g].add(a)
            groups[g].add(b)
        words = text.split()
        options = []
        for word in words:
            g = find(word)
            if g in groups:
                options.append(sorted(groups[g]))
            else:
                options.append([word])
        res = []
        def dfs(i, path):
            if i == len(options):
                res.append(' '.join(path))
                return
            for w in options[i]:
                dfs(i+1, path + [w])
        dfs(0, [])
        return sorted(res)

Rust

use std::collections::{HashMap, BTreeSet};
impl Solution {
    pub fn generate_sentences(synonyms: Vec<Vec<String>>, text: String) -> Vec<String> {
        let mut parent = HashMap::new();
        fn find(x: &str, parent: &mut HashMap<String, String>) -> String {
            if !parent.contains_key(x) { parent.insert(x.to_string(), x.to_string()); }
            if parent[x] != x { let p = parent[x].clone(); parent.insert(x.to_string(), find(&p, parent)); }
            parent[x].clone()
        }
        for p in &synonyms {
            let a = find(&p[0], &mut parent);
            let b = find(&p[1], &mut parent);
            parent.insert(a, b);
        }
        let mut groups: HashMap<String, BTreeSet<String>> = HashMap::new();
        for p in &synonyms {
            let g = find(&p[0], &mut parent);
            groups.entry(g.clone()).or_default().insert(p[0].clone());
            groups.entry(g.clone()).or_default().insert(p[1].clone());
        }
        let words: Vec<&str> = text.split_whitespace().collect();
        let mut options: Vec<Vec<String>> = vec![];
        for word in &words {
            let g = find(word, &mut parent);
            if let Some(set) = groups.get(&g) {
                options.push(set.iter().cloned().collect());
            } else {
                options.push(vec![word.to_string()]);
            }
        }
        let mut res = vec![];
        fn dfs(i: usize, options: &Vec<Vec<String>>, path: Vec<String>, res: &mut Vec<String>) {
            if i == options.len() {
                res.push(path.join(" "));
                return;
            }
            for w in &options[i] {
                let mut new_path = path.clone();
                new_path.push(w.clone());
                dfs(i+1, options, new_path, res);
            }
        }
        dfs(0, &options, vec![], &mut res);
        res.sort();
        res
    }
}

TypeScript

function generateSentences(synonyms: string[][], text: string): string[] {
    const parent: Record<string, string> = {};
    function find(x: string): string {
        if (!(x in parent)) parent[x] = x;
        if (parent[x] !== x) parent[x] = find(parent[x]);
        return parent[x];
    }
    for (const [a, b] of synonyms) parent[find(a)] = find(b);
    const groups: Record<string, Set<string>> = {};
    for (const [a, b] of synonyms) {
        const g = find(a);
        if (!(g in groups)) groups[g] = new Set();
        groups[g].add(a); groups[g].add(b);
    }
    const words = text.split(' ');
    const options: string[][] = words.map(word => {
        const g = find(word);
        if (g in groups) return Array.from(groups[g]).sort();
        return [word];
    });
    const res: string[] = [];
    function dfs(i: number, path: string[]) {
        if (i === options.length) {
            res.push(path.join(' '));
            return;
        }
        for (const w of options[i]) dfs(i+1, [...path, w]);
    }
    dfs(0, []);
    res.sort();
    return res;
}

---

Complexity

• ⏰ Time complexity: O(k^n * n log n) where k is the max synonyms per word, n is number of words
• 🧺 Space complexity: O(k^n * n)