> For the complete documentation index, see [llms.txt](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/backtracking/1258.-synonymous-sentences.md).

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

```cpp
// 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;
}
```

```cpp
// 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;
}
```

```cpp
// 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;
}
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter:

```
GET https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/backtracking/1258.-synonymous-sentences.md?ask=<question>&goal=<endgoal>
```

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.