Share my 0 ms solution, use union find


  • 0
    Y

    if we have b = k0 * a and c = k1*b, we set a as parent of b and b as parent of c, we also need to record the ratio. In this way, we can trace everything back to the original variable.

    class Solution {
        unordered_map<string, double> vmap;
        unordered_map<string, string> rmap;
    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 ++)
            {
                pair<string, string>& p = equations[i];
                rmap[p.first] = p.first;
                rmap[p.second] = p.second;
                vmap[p.first] = vmap[p.second] = 1.0;
            }        
            for(int i = 0; i < equations.size(); i ++)
            {
                pair<string, string>& p = equations[i];
                
                string s = p.first;
                string t = p.second;
                
               
                //s = k * t
                
                double ks = 1.0;
                while(rmap[s] != s)
                {
                    ks *= vmap[s];
                    s = rmap[s];
                }
                
                double ts = 1.0;
                while(rmap[t] != t)
                {
                    ts *= vmap[t];
                    t = rmap[t];
                }
                
                if(s == t)
                    continue;
                
                double k = values[i] * ts / ks;
                if(s < t)
                {
                    swap(s, t);
                    k = 1 / k;
                }
                vmap[s] = k;
                rmap[s] = t;
            }
            
            vector<double> vret;
            for(int i = 0; i < queries.size(); i ++)
            {
                pair<string, string>& p = queries[i];
                string s = p.first;
                string t = p.second;
                
                if(rmap.find(s) == rmap.end() || rmap.find(t) == rmap.end())
                {
                    vret.push_back(-1);
                    continue;
                }
                
                double ks = 1.0;
                while(rmap[s] != s)
                {
                    ks *= vmap[s];
                    s = rmap[s];
                }
                
                double ts = 1.0;
                while(rmap[t] != t)
                {
                    ts *= vmap[t];
                    t = rmap[t];
                }
                
                if(s != t)
                    vret.push_back(-1);
                else
                    vret.push_back(ks / ts);
            }
            
            return vret;
            
        }
    };
    

Log in to reply
 

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