399. Evaluate Division

Problem Statement

link: LeetCode.cn LeetCode

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

You are also given some queries, where queries[j] = [Cj, Dj] represents the jth query where you must find the answer for Cj / Dj = ?.

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.

Note: The variables that do not occur in the list of equations are undefined, so the answer cannot be determined for them.

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]

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]

Solution Approach

The solution utilizes a graph-based approach to evaluate division. It constructs a directed graph where variables are nodes and edges represent division operations, with edge weights representing the result of the division. Then, it performs depth-first search (DFS) to find the result of queries.

Algorithm

1. Construct a graph where each variable is a node and each equation is an edge with its corresponding value as the weight.
2. Traverse the graph using DFS to find paths between variables in the queries.
3. Calculate the result by multiplying edge weights along the path. If no path exists, return -1.

Implement

    class Solution:
    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
      edge = defaultdict(list)
      for i in range(len(equations)):
        x, y = equations[i]
        v = values[i]
        edge[x].append((y, v))
        edge[x].append((x, 1.0/y))
      clusters = []
      visit = set()
      for x, y in equations:
        dic = {}
        if x not in visit:
          start = x
          visit.add(start)
          dic[start] = 1
          q = [start]
          while q:
            cur = q.pop()
            for n, v in edge[cur]:
              if n not in visit:
                visit.add(n)
                q.append(n)
                dic[n] = dic[cur] * v
          clusters.append(dic)
      res = []
      for x, y in queries:
        for cluster in clusters:
          if x in cluster and y in cluster:
            res.append(cluster[y]/ cluster[x])
            break
        else:
          res.append(-1)
      return res        

    
    

Twitter  facebook  Email