# Python solution with detailed explanation

• 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:
return True
else:
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)