Leetcode 399. Evaluate Division

Problem

Leetcode 399 - Evaluate Division

Example:

Input: equations = [["a","b"],["b","c"]], values = [2.0,3.0], queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]
Output: [6.00000,0.50000,-1.00000,1.00000,-1.00000]
Explanation: 
Given: a / 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 ]
note: x is undefined => -1.0

Input: equations = [["a","b"],["b","c"],["bc","cd"]], values = [1.5,2.5,5.0], queries = [["a","c"],["c","b"],["bc","cd"],["cd","bc"]]
Output: [3.75000,0.40000,5.00000,0.20000]

Input: equations = [["a","b"]], values = [0.5], queries = [["a","b"],["b","a"],["a","c"],["x","y"]]
Output: [0.50000,2.00000,-1.00000,-1.00000]

Approach

We can use BFS to save the visited node, and weight inside q. If we reach the target, then we can return w * weight. This works because of simple math where if $\frac{a}{b} * \frac{b}{c} = \frac{a}{c}$

Here is the Python code for the solution:

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

        for i, eq in enumerate(equations):
            a, b = eq
            calc[a].append([b, values[i]])
            calc[b].append([a, 1/values[i]])
        
        def bfs(src, target):
            if src not in calc or target not in calc:
                return -1
            
            q, visit = deque(), set()
            q.append([src, 1])
            visit.add(src)
            while q:
                n, w = q.popleft()
                if n == target:
                    return w
                for nei, weight in calc[n]:
                    if nei not in visit:
                        q.append([nei, w*weight])
                        visit.add(nei)
            return -1
        return [bfs(q[0], q[1]) for q in queries]

Time Complexity and Space Complexity

Time Complexity: $O(n * m)$

Space Complexity: $O(n+m)$