399. Evaluate Division

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

Example:
Givena / 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<double>& values, vector<pair<string, string>> queries, whereequations.size() == values.size(), and the values are positive. This represents the equations. Returnvector<double>.

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.

Thoughts:

1. Explicity building adj list: for permutation of all the pairs of neighbors in one's node i , j, calculate the i , j value as q[i][k] * q[k][j]: assume q[i][i] = 1
2. Union Find
3. DFS

Code: Building adj list: T: O(n^3), S:(n^2)

class Solution(object):
    def calcEquation(self, equations, values, queries):
        """
        :type equations: List[List[str]]
        :type values: List[float]
        :type queries: List[List[str]]
        :rtype: List[float]
        """
        q = collections.defaultdict(dict)

        # build the graph by building the adj list
        for (a, b) , val in zip(equations, values):
            # identity
            q[a][a] = q[b][b] = 1.0
            q[a][b] = val 
            q[b][a] = 1/val

        for k in q:
            for i in q[k]:
                for j in q[k]:
                    q[i][j] = q[i][k] * q[k][j] # connecting nodes explicitly

        return [q[a].get(b, -1.0) for a , b in queries]

Code: DFS + Hash

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>> adj;
        vector<double> res;

        for (int i = 0 ; i < values.size(); i++){
            adj[equations[i].first].insert(make_pair(equations[i].second, values[i]));
            adj[equations[i].second].insert(make_pair(equations[i].first, 1/values[i]));
        }

        for (auto q: queries){
            unordered_set<string> s;
            double tmp = dfs(adj, s, q.first, q.second);
            if(tmp) res.push_back(tmp);
            else res.push_back(-1);
        }

        return res;
    }

private:
    double dfs(unordered_map<string, unordered_map<string, double>>& adj, unordered_set<string>& s, 
               string a, string b){

        if (adj[a].find(b) != adj[a].end()) return adj[a][b];

        for (auto n : adj[a]){
            if(s.find(n.first) == s.end()){
                s.insert(n.first);
                double tmp =  dfs(adj, s, n.first, b);
                if (tmp) return n.second * tmp; 
            }
        }

        return 0; // did not find
    }

};

Code: Union Find

class Solution(object):
    def calcEquation(self, equations, values, queries):
        """
        :type equations: List[List[str]]
        :type values: List[float]
        :type queries: List[List[str]]
        :rtype: List[float]
        """
        def union(n1, n2, val):
            p1, p2 = find(n1), find(n2)
            r = n2.value * val / n1.value # v(n1) * val = v(n2) * r , r = v(n1) * val / v(n2)

            # doing the reverse linear searching for p1's child in the map, normalize the value
            for entry in m.values():
                if find(entry) == p1:
                    entry.value *= r  
            p1.parent = p2


        def find(node):
            while node.parent!= node:
                # node.parent = node.parent.parent
                node = node.parent
            return node

        m, res = {}, []

        for i, (a , b) in enumerate(equations):
            value = values[i]
            if a not in m and b not in m:
                node_a, node_b = Node(), Node()
                node_a.value = value
                node_a.parent = node_b
                node_b.value = 1
                m[a] = node_a
                m[b] = node_b

            elif a not in m:
                node_a = Node()
                node_a.value = m[b].value * value
                node_a.parent = m[b]
                m[a] = node_a

            elif b not in m:
                node_b = Node()
                node_b.value = m[a].value / value
                node_b.parent = m[a] # order switched
                m[b] = node_b

            else:
                union(m[a], m[b], value)

        for a, b in queries:
            if a not in m or b not in m or find(m[a]) != find(m[b]):
                res.append(-1)

            else:
                res.append(m[a].value/m[b].value)

        return res

class Node(object):
    def __init__ (self):
        self.parent = self
        self.value = 0