leetcode-399-Evaluate Division

Equations are given in the format A / B = k, where A and B are variables represented as strings, and k is a real number (floating point number). Given some queries, return the answers. If the answer does not exist, return -1.0.

Example:
Given a / b = 2.0, b / c = 3.0.
queries are: a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ? .
return [6.0, 0.5, -1.0, 1.0, -1.0 ].

The input is: vector<pair<string, string>> equations, vector& values, vector<pair<string, string>> queries , where equations.size() == values.size(), and the values are positive. This represents the equations. Return vector.

According to the example above:

equations = [ ["a", "b"], ["b", "c"] ],
values = [2.0, 3.0],
queries = [ ["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"] ].

The input is always valid. You may assume that evaluating the queries will result in no division by zero and there is no contradiction.

形如给定a/b和b/c，让求a/c，可以抽象成图论求各结点之间的距离．因为是多点到多点的方式，所以可以用Floyd 算法来算．这个算法应该是图论中最简单粗暴的算法了，相比prime和dijkstra算法不仅容易理解，还很容易实现．只要三重循环即可，其中最外层是中间结点．还有要注意的是如果queries的是两个相同数如a/a这种自己设置一下即可．

class Solution {
public:
    vector<double> calcEquation(vector<pair<string, string>> equations, 
        vector<double>& values, vector<pair<string, string>> queries) {
        unordered_map<string, unordered_map<string, double>> hash;
        for(int i = 0; i < equations.size(); i++) 
        {
            hash[equations[i].first][equations[i].second] = values[i];
            hash[equations[i].second][equations[i].first] = 1/values[i];
        }
        for(auto val: hash) hash[val.first][val.first] = 1;
        for(auto val1: hash)
        {
            for(auto val2: hash)
                for(auto val3: hash)
                    if(hash[val1.first].count(val3.first) 
                            && hash[val2.first].count(val1.first))
                        hash[val2.first][val3.first] = 
                            hash[val2.first][val1.first]*hash[val1.first][val3.first];
        }
        vector<double> ans;
        for(auto val: queries)
            ans.push_back(hash[val.first].count(val.second)?hash[val.first][val.second]:-1);
        return ans;
    }
};

dfs:

class Solution {
private:
    unordered_map<string, unordered_map<string, double>> m;
public:    
    double findPath(string start, string end, unordered_map<string, bool> &visited) {
        visited[start] = true;
        
        if(m[start].find(end) != m[start].end()) {
            return m[start][end];
        }
        
        for(auto neighbours: m[start]) {
            if(visited.find(neighbours.first) == visited.end()) {
                double result = findPath(neighbours.first, end, visited);
                if(result != -1) {
                    return result * m[start][neighbours.first];
                }
            }
        }
        return -1;
    }
    
    vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries) {
        vector<double> result;
        for(int i = 0; i < equations.size(); i++) {
            m[equations[i].first][equations[i].first] = 1;
            m[equations[i].second][equations[i].second] = 1;
            m[equations[i].first][equations[i].second] = values[i];
            m[equations[i].second][equations[i].first] = 1 / values[i];
        }
        
        for(auto query: queries) {
            unordered_map<string, bool> v;
            result.push_back(findPath(query.first, query.second, v));
        }
        
        return result;
    }
};

bfs:

1 - Build a directed, weighted graph for every string couple in equations (a, b) => a->{b, weight} where weight comes from the second input vector.
2 - For every query (s1, s2): run BFS from s1 to s2. Keep multiplying the weights, and if s2 is reached return the product.

double BFS(string a, string b, unordered_map>>& g) {
        if(g.count(a) == 0 || g.count(b) == 0) return -1.0; // Any string does not exist in graph
        if(a == b) return 1.0; // same  string (s/s)
        queue> q;
        q.push({a, 1.0});
        unordered_set visited;
        while(!q.empty()) { 
            pair curr = q.front(); 
            q.pop();
            visited.insert(curr.first);
            if(curr.first == b) return curr.second;
            for(auto &p : g[curr.first])
                if(visited.count(p.first) == 0) q.push({p.first, p.second*curr.second});
        }
        return -1.0;
    }
public:
    vector calcEquation(vector> e, vector& v, vector> q) {
        unordered_map>> g;
        for(int i = 0; i < e.size(); i++) { // Build a graph (weighted, directed)
            g[e[i].first].push_back({e[i].second, v[i]});
            g[e[i].second].push_back({e[i].first, 1.0/v[i]});
        }
        vector res(q.size());
        for(int i = 0; i < q.size(); i++) res[i] = BFS(q[i].first, q[i].second, g);
        return res;
    }