Concise 0ms C++ solution using Union-Find


  • 0
    W
    class Solution {
    public:
        vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries) {
            for(int i=0;i<equations.size();i++){
                string p = equations[i].first;
                string q = equations[i].second;
                if(id.find(p) == id.end())  id[p] = make_pair(p, 1);
                if(id.find(q) == id.end())  id[q] = make_pair(q, 1);
                unionFind(p, q, values[i]);
            }
        
            vector<double> res;
            for(int i=0;i<queries.size();i++){
                string p = queries[i].first;
                string q = queries[i].second;
                if(id.find(p) == id.end() || id.find(q) == id.end() || find(p).first != find(q).first)
                    res.push_back(-1);
                else
                    res.push_back(find(p).second / find(q).second);
            }
            return res;
        }
        
        void unionFind(string p, string q, double v){
            pair<string, double> proot = find(p);
            pair<string, double> qroot = find(q);
            id[proot.first].first = qroot.first;
            id[proot.first].second = (v * qroot.second)/proot.second;
        }
        
        
        pair<string, double> find(string p){
            double value = 1;
            while(p != id[p].first){
                id[p].second = id[p].second * id[id[p].first].second;
                id[p].first  = id[id[p].first].first;
                value = value * id[p].second;
                p = id[p].first;
            }
            return make_pair(p, value);
        }
    
    private:
        unordered_map <string, pair<string, double>> id;
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.