Leetcode 1258: Synonymous Sentences

https://leetcode.com/problems/synonymous-sentences/description/

Notes:

This is not a straightforward question.

If we know the equivalent words for each word in the text, then this question becomes straightforward: a typical combination problem which can be solved by dfs.

So the key is how to find the equivalent words?

For any two synonyms[i] and synonyms[j], if they have at least one the same string, all the strings become equivalent, or belong to the same group. So we can apply union-find like algorithm to solve grouping problem.

The next detail is that how do we know the word in the text have equivalent words? Here we can use a hash map to record all the words in the synonyms. We also want to know which group the words belong to. So the value of the hash map can be set as the group number.

See the code below:

class Solution {
public:
    vector<string> generateSentences(vector<vector<string>>& synonyms, string text) {
        int n = synonyms.size();
        vector<int> ps(n, 0);//initialization of parents in union-find
        for(int i=0; i<ps.size(); ++i) ps[i] = i;
        vector<int> visit(n, 0);
        for(int i=0; i<n; ++i) {//brute force to find groups
            if(visit[i]) continue;
            for(auto &a : synonyms[i]) {
                for(int j= i+1; j<n; ++j) {
                    if(visit[j]) continue;
                    for(auto &b : synonyms[j]) {
                        if(a == b) {ps[j] = i; visit[j] = 1; break;}
                    }
                }
            }
        }
        unordered_map<int, set<string>> mp1;
        unordered_map<string, int> mp2;
        for(int i=0; i<n; ++i) {
            for(auto &a : synonyms[i]) {
                mp1[ps[i]].insert(a);
                mp2[a] = ps[i];
            }
        }
        vector<string> res;
        dfs(text, 0, "", mp2, mp1, res);
        sort(res.begin(), res.end());
        return res;
    }

private:
    void dfs(string s, int idx, string one, unordered_map<string, int>& mp2, unordered_map<int, set<string>>& mp1, vector<string>& res) {
        if(idx >= s.size()) {res.push_back(one); return;}
        int i = idx;
        while(i<s.size() && s[i] != ' ') ++i;
        string t = s.substr(idx, i-idx);
        if(!mp2.count(t)) {
            if(i < s.size()) t.push_back(' ');
            return dfs(s, i+1, one+t, mp2, mp1, res);
        }
        int r = mp2[t];
        for(auto a = mp1[r].begin(); a != mp1[r].end(); ++a) {
            string t1 = *a;
            if(i<s.size()) t1.push_back(' ');
            dfs(s, i+1, one + t1, mp2, mp1, res);
        }
    }
};