C++, Union Find solution.


  • 0
    class Solution {
    public:
        vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries) {
            unordered_map<string, pair<string, double>> track;
            for(int i = 0;i < equations.size();i++)
            {
                track[equations[i].first] = make_pair(equations[i].first,1.0);
                track[equations[i].second] = make_pair(equations[i].second,1.0);
            }
            
            for(int i = 0;i < equations.size();i++)
            {
                string left = equations[i].first;
                double lv = 1.0;
                while(track[left].first != left)
                {
                    lv = lv * track[left].second;
                    left = track[left].first;
                }
                string right = equations[i].second;
                double rv = 1.0;
                while(track[right].first != right)
                {
                    rv = rv * track[right].second;
                    right = track[right].first;
                }
                
                track[left].second  = (rv * values[i]) / lv;
                track[left].first = right;
            }
            vector<double> res(queries.size());
            for(int i = 0;i < queries.size();i++)
            {
                string left = queries[i].first;
                string right = queries[i].second;
                if(track.find(left) == track.end())
                {
                    res[i] = -1.0; continue;
                }
                else if(track.find(right) == track.end())
                {
                    res[i] = -1.0;continue;
                }
                double lv = 1.0;
                while(track[left].first != left)
                {
                    lv = lv * track[left].second;
                    left = track[left].first;
                }
                double rv = 1.0;
                while(track[right].first != right)
                {
                    rv = rv * track[right].second;
                    right = track[right].first;
                }
                if(left != right)
                {
                    res[i] = -1.0;
                    continue;
                }
                else
                {
                    res[i] = lv / rv;
                }
            }
            return res; 
        }
    };
    

Log in to reply
 

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