LeetCode Top Interview 150

399. Evaluate Division

Medium

You are given an array of variable pairs equations and an array of real numbers values, where equations[i] = [A_i, B_i] and values[i] represent the equation A_i / B_i = values[i]. Each A_i or B_i is a string that represents a single variable.

You are also given some queries, where queries[j] = [C_j, D_j] represents the j^th query where you must find the answer for C_j / D_j = ?.

Return the answers to all queries. If a single answer cannot be determined, return -1.0.

Note: The input is always valid. You may assume that evaluating the queries will not result in division by zero and that there is no contradiction.

Example 1:

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 ]

Example 2:

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]

Example 3:

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]

Constraints:

1 <= equations.length <= 20
equations[i].length == 2
1 <= A_i.length, B_i.length <= 5
values.length == equations.length
0.0 < values[i] <= 20.0
1 <= queries.length <= 20
queries[i].length == 2
1 <= C_j.length, D_j.length <= 5
A_i, B_i, C_j, D_j consist of lower case English letters and digits.

Solution

from typing import Dict, List

class Solution:
    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
        self.root: Dict[str, str] = {}
        self.rate: Dict[str, float] = {}
        
        # Initialize all variables
        for equation in equations:
            x, y = equation[0], equation[1]
            self.root[x] = x
            self.root[y] = y
            self.rate[x] = 1.0
            self.rate[y] = 1.0
        
        # Union all equations
        for i, equation in enumerate(equations):
            x, y = equation[0], equation[1]
            self.union(x, y, values[i])
        
        # Process queries
        result = []
        for query in queries:
            x, y = query[0], query[1]
            if x not in self.root or y not in self.root:
                result.append(-1.0)
                continue
            
            root_x = self.findRoot(x, x, 1.0)
            root_y = self.findRoot(y, y, 1.0)
            
            if root_x == root_y:
                result.append(self.rate[x] / self.rate[y])
            else:
                result.append(-1.0)
        
        return result
    
    def union(self, x: str, y: str, v: float) -> None:
        root_x = self.findRoot(x, x, 1.0)
        root_y = self.findRoot(y, y, 1.0)
        self.root[root_x] = root_y
        r1 = self.rate[x]
        r2 = self.rate[y]
        self.rate[root_x] = v * r2 / r1
    
    def findRoot(self, original_x: str, x: str, r: float) -> str:
        if self.root[x] == x:
            self.root[original_x] = x
            self.rate[original_x] = r * self.rate[x]
            return x
        return self.findRoot(original_x, self.root[x], r * self.rate[x])

This site is open source. Improve this page.