1258

1258. Synonymous Sentences (Medium)

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

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.
• The words of text are separated by single spaces.

Companies:
Cruise Automation

Related Topics:
Array, Hash Table, String, Backtracking, Union Find

Solution 1.

// OJ: https://leetcode.com/problems/synonymous-sentences/
// Author: github.com/lzl124631x
// Time: O(NlogN)
// Space: O(N)
class UnionFind {
    vector<int> id;
public:
    UnionFind(int N) : id(N) {
        iota(begin(id), end(id), 0);
    }
    int find(int a) {
        return id[a] == a ? a : (id[a] = find(id[a]));
    }
    void connect(int a, int b) {
        id[find(a)] = find(b);
    }
};
class Solution {
public:
    vector<string> generateSentences(vector<vector<string>>& A, string s) {
        istringstream ss(s);
        string word;
        vector<string> v, tmp, ans;
        while (ss >> word) v.push_back(word);
        int id = 0;
        unordered_map<string, int> index;
        unordered_map<int, string> rindex;
        for (auto &syn : A) {
            if (index.count(syn[0]) == 0) {
                index[syn[0]] = id;
                rindex[id] = syn[0];
                ++id;
            }
            if (index.count(syn[1]) == 0) {
                index[syn[1]] = id;
                rindex[id] = syn[1];
                ++id;
            }
        }
        UnionFind uf(index.size());
        for (auto &syn : A) {
            uf.connect(index[syn[0]], index[syn[1]]);
        }
        unordered_map<int, set<string>> m;
        for (int i = 0; i < index.size(); ++i) {
            m[uf.find(i)].insert(rindex[i]);
        }
        function<void(int)> dfs = [&](int i) {
            if (i == v.size()) {
                string t;
                for (auto &w : tmp) {
                    if (t.size()) t += ' ';
                    t += w;
                }
                ans.push_back(t);
                return;
            }
            if (index.count(v[i])) {
                for (auto &syn : m[uf.find(index[v[i]])]) {
                    tmp.push_back(syn);
                    dfs(i + 1);
                    tmp.pop_back();
                } 
            } else {
                tmp.push_back(v[i]);
                dfs(i + 1);
                tmp.pop_back();
            }
        };
        dfs(0);
        return ans;
    }
};

TODO

Too lengthy. Find better solution.