Although this looks like a math problem, we can easily model it with graph.
Given:
a/b = 2.0, b/c = 3.0
We can build a directed graph:
a -- 2.0 --> b -- 3.0 --> c
If we were asked to find a/c, we have:
a/c = a/b * b/c = 2.0 * 3.0
In the graph, it is the product of costs of edges.
Do notice that, 2 edges need to added into the graph with one given equation, because with a/b we also get result of b/a, which is the reciprocal of a/b.
so the previous example also gives edges:
c -- 0.333 --> b -- 0.5 --> a
Now we know how to model this problem, what we need to do is simply build the graph with given equations, and traverse the graph, either DFS or BFS, to find a path for a given query, and the result is the product of costs of edges on the path.
One optimization, which is not implemented in the code, is to "compress" paths for past queries, which will make future searches faster. This is the same idea used in compressing paths in union find set. So after a query is conducted and a result is found, we add two edges for this query if these edges are not already in the graph.
Given the number of variables N, and number of equations E, building the graph takes O(E), each query takes O(N), space for graph takes O(E)
Complexity T : O(E) / O(N) M : O(N)
class Solution:
def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
graph = {}
def build_graph(equations, values):
def add_edge(f, t, value):
if f in graph:
graph[f].append((t, value))
else:
graph[f] = [(t, value)]
for vertices, value in zip(equations, values):
f, t = vertices
add_edge(f, t, value)
add_edge(t, f, 1/value)
def find_path(query):
b, e = query
if b not in graph or e not in graph:
return -1.0
q = collections.deque([(b, 1.0)])
visited = set()
while q:
front, cur_product = q.popleft()
if front == e:
return cur_product
visited.add(front)
for neighbor, value in graph[front]:
if neighbor not in visited:
q.append((neighbor, cur_product*value))
return -1.0
build_graph(equations, values)
return [find_path(q) for q in queries]