Disgusting c++ solution


  • 0

    Simple DFS solution using pair to keep precision as high as possible.
    A/B saved as pair(A, B), Only divide at final step.

    vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries) {
        unordered_map<pair<string, string>, pair<double, double>, string_pair_hash> expressions;
        unordered_map<string, unordered_set<string>> pairs;
        int size = equations.size();
        for (int i = 0; i < size; i++) {
            expressions[make_pair(equations[i].first, equations[i].second)] = make_pair(values[i], 1);
            expressions[make_pair(equations[i].second, equations[i].first)] = make_pair(1, values[i]);
            pairs[equations[i].first].insert(equations[i].second);
            pairs[equations[i].second].insert(equations[i].first);
        }
        vector<double> results;
        for (auto query : queries) {
            unordered_set<string> accessed;
            accessed.insert(query.first);
            accessed.insert(query.second);
            pair<double, double> result = calculate(expressions, query, pairs, accessed);
            results.push_back(result.first == 0 && result.second == 0 ? -1.0 : result.first / result.second);
        }
        return results;
    }
    
    struct string_pair_hash {
        std::size_t operator () (const pair<string, string> &p) const {
            return p.first.size() ^ p.second.size();
        }
    };
    
    pair<double, double> calculate(unordered_map<pair<string, string>, pair<double, double>, string_pair_hash> &expressions,
                                   pair<string, string> p,
                                   unordered_map<string, unordered_set<string>> &pairs,
                                   unordered_set<string> &accessed) {
        if (expressions.find(p) != expressions.end())
            return expressions[p];
        pair<double, double> result = make_pair(0.0, 0.0);
        for (auto s : pairs[p.first]) {
            if (accessed.find(s) == accessed.end()) {
                accessed.insert(s);
                pair<double, double> next = calculate(expressions, make_pair(s, p.second), pairs, accessed);
                if (next.first != 0 || next.second != 0) {
                    pair<double, double> current = expressions[make_pair(p.first, s)];
                    result.first = current.first * next.first;
                    result.second = current.second * next.second;
                    break;
                }
            }
        }
        return result;
    }
    

Log in to reply
 

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