737. Sentence Similarity II

We can represent a sentence as an array of words, for example, the sentence “I am happy with leetcode” can be represented as arr = [“I”,”am”,happy”,”with”,”leetcode”].

Given two sentences sentence1 and sentence2 each represented as a string array and given an array of string pairs similarPairs where similarPairs[i] = [xi, yi] indicates that the two words xi and yi are similar.

Return true if sentence1 and sentence2 are similar, or false if they are not similar.

Two sentences are similar if:

• They have the same length (i.e., the same number of words)
• sentence1[i] and sentence2[i] are similar.

Notice that a word is always similar to itself, also notice that the similarity relation is transitive. For example, if the words a and b are similar, and the words b and c are similar, then a and c are similar.

• Time : O((p + n)logp) [log p on find, for each point and sentence]
• Space : O(p)

class Solution {
    unordered_map<string, int> match;
    unordered_map<int, int> gr;

    int find(int n) {
        return gr[n] == n ? n : gr[n] = find(gr[n]);
    }
    void uni(string& s1, string& s2) {
        int ps1 = find(match[s1]), ps2 = find(match[s2]);
        gr[ps1] = gr[ps2] = min(ps1,ps2);
    }
public:
    bool areSentencesSimilarTwo(vector<string>& s1, vector<string>& s2, vector<vector<string>>& p) {
        if(s1.size() != s2.size()) return false;
        int groupCount = 1;
        for(auto vec : p) {
            if(!match.count(vec[0])) {
                gr[groupCount] = groupCount;
                match[vec[0]] = groupCount++;
            }
            if(!match.count(vec[1])) {
                gr[groupCount] = groupCount;
                match[vec[1]] = groupCount++;
            }
            uni(vec[0], vec[1]);
        }
        for(int i = 0; i < s1.size(); i++) {
            if(s1[i] == s2[i]) continue;
            if(!match.count(s1[i]) or !match.count(s2[i])) return false;
            if(find(match[s1[i]]) != find(match[s2[i]])) return false;
        }
        return true;
    }
};