Evaluate Division

Description

Equations are given in the format A / B = k, where A and B are variables represented as strings, and k is a real number (floating point number). Given some queries, return the answers. If the answer does not exist, return -1.0.

Example:
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 ].

The input is: vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries , where equations.size() == values.size(), and the values are positive. This represents the equations. Return vector<double>.

According to the example above:

equations = [ ["a", "b"], ["b", "c"] ],
values = [2.0, 3.0],
queries = [ ["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"] ]. 

 

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

Solution(javascript)

/** DFS
 * @param {string[][]} equations
 * @param {number[]} values
 * @param {string[][]} queries
 * @return {number[]}
 */
const calcEquation = function (equations, values, queries) {
  const adj = equations.reduce((acc, [dividend, divisor], index) => {
    acc[dividend] = acc[dividend] || []
    acc[divisor] = acc[divisor] || []
    acc[dividend].push([divisor, values[index]])
    acc[divisor].push([dividend, 1 / values[index]])
    return acc
  }, {})
  const bfs = (src, target) => {
    if (src === target && adj[src]) {
      return 1.0
    }
    let current = adj[src] || []
    const visited = { [src]: true }
    while (current.length > 0) {
      const nextList = []
      for (const [next, value] of current) {
        if (!visited[next]) {
          visited[next] = true
          if (next === target) {
            return value
          }
          adj[next].forEach(([next2, value2]) => {
            nextList.push([next2, value * value2])
          })
        }
      }
      current = nextList
    }
    return -1
  }
  return queries.map(([src, target]) => bfs(src, target))
}