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.

// Find with path compression
string findRoot(unordered_map<string, string>& roots, const string& s) {
    return roots[s] == s ? s : roots[s] = findRoot(roots, roots[s]);
}
void dfs(unordered_map<string, string>& roots, unordered_set<string>& words, int start, string& text, vector<string>& res) {
    if (start >= text.length()) { // actually there is no equality case in this code
        res.emplace_back(text);
        return;
    }
    string cur; // current word
    int idx;
    for (idx = start; idx < text.length() && text[idx] != ' '; ++idx) {
        cur += text[idx];
    }
    ++idx; // skip whitespace
    // Keep the current word unchanged
    dfs(roots, words, idx, text, res);
    string pre = text;
    // Change the current word with its synonyms
    if (roots.count(cur)) {
        for (const string& word : words) {
            if (cur != word && findRoot(roots, cur) == findRoot(roots, word)) {
                text.replace(start, cur.length(), word);
                dfs(roots, words, idx - cur.length() + word.length(), text, res);
                text = pre; // reset to the previous state before replacement
            }
        }
    }
}
// Union Find + DFS
vector<string> generateSentences(vector<vector<string>>& synonyms, string text) {
    unordered_map<string, string> roots;
    unordered_map<string, int> root_sz;
    unordered_set<string> words;
    // Union
    for (const vector<string>& syn : synonyms) {
        if (!roots.count(syn[0])) {
            roots[syn[0]] = syn[0];
            root_sz[syn[0]] = 1;
        }
        if (!roots.count(syn[1])) {
            roots[syn[1]] = syn[1];
            root_sz[syn[1]] = 1;
        }
        words.insert(syn[0]);
        words.insert(syn[1]);
        string r1 = findRoot(roots, syn[0]), r2 = findRoot(roots, syn[1]);
        if (r1 != r2) {
            if (root_sz[r1] >= root_sz[r2]) roots[r2] = r1;
            else roots[r1] = r2;
        }
    }
    vector<string> res;
    // Backtracking
    dfs(roots, words, 0, text, res);
    // Sort lexicographically
    sort(res.begin(), res.end());
    return res;
}

// Find with path compression
string getRoot(unordered_map<string, string>& roots, const string& s) {
    return roots[s] == s ? s : roots[s] = getRoot(roots, roots[s]);
}
vector<string> dfs(unordered_map<string, string>& roots, unordered_map<string, vector<string> >& unioned_synonyms, const vector<string>& words, int pos) {
    if (pos == words.size()) return {""};
    vector<string> right_res = dfs(roots, unioned_synonyms, words, pos + 1);
    vector<string> res;
    for (string& s : right_res) {
        if (!s.empty()) s = " " + s;
        if (roots.count(words[pos])) {
            string root = getRoot(roots, words[pos]);
            for (const string& syn : unioned_synonyms[root]) {
                res.emplace_back(syn + s);
            }
        } else {
            res.emplace_back(words[pos] + s);
        }
    }
    return res;
}
// Union Find + DFS
vector<string> generateSentences(vector<vector<string>>& synonyms, string text) {
    unordered_map<string, string> roots;
    for (const vector<string>& p : synonyms) {
        string u = p[0], v = p[1];
        if (!roots.count(u)) roots[u] = u;
        if (!roots.count(v)) roots[v] = v;
        string r1 = getRoot(roots, u), r2 = getRoot(roots, v);
        if (r1 != r2) roots[r2] = r1;
    }
    unordered_map<string, vector<string> > unioned_synonyms;
    for (auto& entry : roots) {
        string root = getRoot(roots, entry.first);
        unioned_synonyms[root].emplace_back(entry.first);
    }
    vector<string> words;
    istringstream iss(text);
    string word;
    while (iss >> word) words.emplace_back(word);
    vector<string> res = dfs(roots, unioned_synonyms, words, 0);
    sort(res.begin(), res.end());
    return res;
}

// Find with path compression
string getRoot(unordered_map<string, string>& roots, const string& s) {
    return roots[s] == s ? s : roots[s] = getRoot(roots, roots[s]);
}
vector<string> dfs(unordered_map<string, string>& roots, const vector<string>& words, int pos) {
    if (pos == words.size()) return {""};
    vector<string> right_res = dfs(roots, words, pos + 1);
    vector<string> res;
    for (string& s : right_res) {
        if (!s.empty()) s = " " + s;
        if (roots.count(words[pos])) {
            string root = getRoot(roots, words[pos]);
            for (auto& e : roots) {
                if (getRoot(roots, e.first) == root) {
                    res.emplace_back(e.first + s);
                }
            }
        } else {
            res.emplace_back(words[pos] + s);
        }
    }
    return res;
}
// Union Find + DFS
vector<string> generateSentences(vector<vector<string>>& synonyms, string text) {
    unordered_map<string, string> roots;
    for (const vector<string>& p : synonyms) {
        string u = p[0], v = p[1];
        if (!roots.count(u)) roots[u] = u;
        if (!roots.count(v)) roots[v] = v;
        string r1 = getRoot(roots, u), r2 = getRoot(roots, v);
        if (r1 != r2) roots[r2] = r1;
    }
    vector<string> words;
    istringstream iss(text);
    string word;
    while (iss >> word) words.emplace_back(word);
    vector<string> res = dfs(roots, words, 0);
    sort(res.begin(), res.end());
    return res;
}