Python solution with detailed explanation


  • 0
    G

    Solution

    Evaluate Division https://leetcode.com/problems/evaluate-division/

    • Model the problem as a graph. a/b = 2.0 would be modelled as 2 nodes a and b and an edge from a to b as 2.0.
    • Represent the graph as a dictionary of dictionary. graph[a] = {b:2.0} and graph[b] = {a:0.5}.
    • Now solving any query x1/y1 is a dfs from x1 with terminal position y1 while multiplying the edge value along the way. Note that we design DFS method so that it returns True when the search is complete.
    • Be careful about input like "x"/"x" - return False from DFS and return -1. Look at the code how we accomplish this.
    class Solution(object):
        def evaluate(self, graph, start, end, so_far, visited):
            if start not in graph:
                return False
            elif start == end:
                self.answer = so_far
                return True
            else:
                visited.add(start)
                candidates = (nbr for nbr in graph[start] if nbr not in visited)
                for nbr in candidates:
                    if self.evaluate(graph, nbr, end, so_far*graph[start][nbr], visited):
                        return True
                return False
        
        def build_graph(self, equations, values):
            graph = {}
            for idx, equation in enumerate(equations):
                x1, y1 = equation[0], equation[1]
                graph.setdefault(x1, {})
                graph.setdefault(y1, {})
                graph[x1][y1],graph[y1][x1] = values[idx], 1.0/values[idx]
            return graph
        
        def calcEquation(self, equations, values, queries):
            """
            :type equations: List[List[str]]
            :type values: List[float]
            :type queries: List[List[str]]
            :rtype: List[float]
            """
            graph = self.build_graph(equations, values)
            result, self.answer = [], None
            for query in queries:
                answer = self.answer if self.evaluate(graph, query[0], query[1], 1.0, set([])) else -1
                result.append(answer)
            return result
    

Log in to reply
 

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