Straightforward C++ recursion


  • 0
    B
    class Solution {
    public:
        double calc(map<string, map<string, double>> & m, string a, string b, set<string> & used) {
            if(used.count(a)) return -1;
            if(m.count(a) == 0 || m.count(b)==0) return -1;
            if(a == b) return 1;
            map<string, double> & m1 = m[a];
            for(auto &v:m1) {
                if(v.first == b) return v.second;
            }
            used.insert(a);
            for(auto &v:m1) {
                double ret = calc(m, v.first, b, used);
                if(ret != -1) return v.second*ret;
            }
            used.erase(a);
            return -1;
        }
    
        vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries) {
            map<string, map<string, double>> m;
            for(int i=0;i<equations.size();i++) {
                m[equations[i].first].emplace(equations[i].second, values[i]);
                if(values[i]) m[equations[i].second].emplace(equations[i].first, 1/values[i]);
            }
            vector<double> ret;
            for(auto a:queries) {
                set<string> used;
                ret.push_back(calc(m, a.first, a.second, used));
            }
            return ret;
        }
    };
    

Log in to reply
 

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