399.Evaluate Division

Tags: [graph], [BFS], [backtrace], [build_path], [map], [union_find]

Link: https://leetcode.com/problems/evaluate-division/?tab=Description

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.

Solution: BFS, backtrace

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]
        """
        if not equations or not values or not queries:
            return []

        graph = {}
        equation_value_map = {}

        # build the graph
        for i in xrange(len(equations)):
            node1, node2 = equations[i][0], equations[i][1]
            value = values[i]

            self.build_edge(node1, node2, value, graph, equation_value_map)
            self.build_edge(node2, node1, 1.0/value, graph, equation_value_map)

        result = []
        for query in queries:
            node1, node2 = query[0], query[1]
            result.append(self.search(graph, equation_value_map, node1, node2))

        return result

    def build_edge(self, node1, node2, value, graph, equation_value_map):
        if node1 not in graph:
            graph[node1] = set([node2])
        else:
            graph[node1].add(node2)

        if node2 not in graph:
            graph[node2] = set([node1])
        else:
            graph[node2].add(node1)

        edge_str = '{}-{}'.format(node1, node2)
        if edge_str not in equation_value_map:
            equation_value_map[edge_str] = value

    def search(self, graph, equation_value_map, start, end):
        # BFS (Breadth First Search)
        parent = {}
        visited = set([start])
        queue = [start]
        path = []

        while queue:
            curr = queue.pop(0)
            if curr not in graph:
                break
            if curr == end:
                path = self.backtrace_build_path(parent, start, end)
                break

            # iterate all nodes connecting to the curr
            for v in graph[curr]:
                if v not in visited:
                    visited.add(v)
                    parent[v] = curr
                    queue.append(v)

        if not path:
            return -1.0
        else:
            result = 1.0
            for i in xrange(len(path) - 1):
                node1, node2 = path[i], path[i + 1]
                edge_str = '{}-{}'.format(node1, node2)
                if edge_str in equation_value_map:
                    result *= equation_value_map[edge_str]

            return result

    def backtrace_build_path(self, parent, start, end):
        path = [end]
        while path[-1] != start:
            path.append(parent[path[-1]])
        path.reverse()
        return path

Revelation:

• To solve this problem, we build a directed weight graph. For example, ['a', 'b'] => a/b = 2.0, we can get another direction, ['b', 'a'] => b/a = 1.0/2.0. So there are two nodes, 'a' and 'b', the weight(from 'a' to 'b') = 2.0, the weight(from 'b' to 'a') = 1.0/2.0.
• For each query, we can treat as that query = [node1, node2], and we try to find a path from node1 to node2, then multiply all the weights between the nodes on the path.
• When we maintain the 'parent' map during the BFS, we only set the relationship between parent and nodes one time. We know for one node, it may have multiple parents, but we only record the very beginning relationship, because we are doing the BFS, the shortest path should be showed early.

• For example, node C has two parents, A and B. But if our BFS starts from A, so first we put A into the queue and visited, then dequeue to get A, then iterate all nodes which are connecting with A, which should be B and C, and at this moment, parent[B] = A, and parent[C] = A, then put B and C into the queue, and at the same time, put B and C into visited.When we dequeue to get the C, we need iterate all C's connected nodes, so we get A and B, now we don't need to set parent[B] = C or parent[B] = [A, C], because A is 'start', from B to A is shorter than B to C to A.
• We can also use union-find data structure and algorithm to get whether node1 and node2 are connected, but I don't know after that how to get the result, if we don't find the path.

Note:

• Time complexity = O(n + m * k), n is the number of equations, m is number of queries, and k is number of 'nodes'.