399. Evaluate Division

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

Python

Backtracking (Offical Solution)

• 因為a/c = a/b * b/c，所以將整個equations/values的對應變成一個有向圖
• 在圖內出發(被除數)找得到path到達目的(除數)，path的node相乘就會是答案

from collections import defaultdict

class Solution:
    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:

        def backtrack(curr_node, target_node, acc_product, visited):
            neighbors = graph[curr_node]
            if target_node in neighbors:
                return acc_product * neighbors[target_node]

            visited.add(curr_node)

            for neighbor, value in neighbors.items():
                if neighbor in visited:
                    continue

                ret = backtrack(
                    neighbor,
                    target_node,
                    acc_product * value,
                    visited
                )
                if ret != -1.0:
                    return ret

            visited.remove(curr_node)

            return -1.0

        # 1. build the graph from the equations
        graph = defaultdict(defaultdict)
        for i, pair in enumerate(equations):
            dividend, divisor = pair
            graph[dividend][divisor] = values[i]
            graph[divisor][dividend] = 1 / values[i]

        # 2. Evaluate each query with backtracking
        results = []
        for dividend, divisor in queries:
            if dividend not in graph or divisor not in graph:
                # Either node does not exist
                results.append(-1.0)
            elif dividend == divisor:
                # Origin and destination are the same node
                results.append(1.0)
            else:
                result = backtrack(dividend, divisor, 1, set())
                results.append(result)

        return results