Leetcode 399: Evaluate division

leetcode_399.md

Description

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.

Link to the original problem

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 <= Ai.length, Bi.length <= 5
• values.length == equations.length
• 0.0 < values[i] <= 20.0
• 1 <= queries.length <= 20
• queries[i].length == 2
• 1 <= Cj.length, Dj.length <= 5
• Ai, Bi, Cj, Dj consist of lower case English letters and digits.

Idea

1. If you never worked on problems like this, it might be a bit tricky to figure out the solution. If you already have experience, this one can be an easy question.
2. Assume this is first time we saw this question, we can work on some examples, like we did last time. We may figure something out on the way.
3. So let's take the first example, given a / b = 2, b / c = 3, how do you caculate a / c? I mean, mathematically, it's fairly simple, it's 6, since a = 2 * b = 2 * 3 * c, so a / c = 6.
4. However, we need to think like a computer does. I mean, this list of computation can potentionally go on and on, like a / b = 2, b / c = 3, c / d = 4, d / e = 5, ... and it might ask what a / z is. So the computer need a way to "express" this problem and somehow calculate the answer using some data structures it's familiar with.
5. So which data structure is best for this problem? Array? List? Queue? Stack? Matrix? Graph?
6. You'll probably realize now that it should be graph!
7. Why? Because the "variables" are the "nodes", the "values" are the "weights" of the edges between the nodes. Make sense, right? And the edges are directed, because a / b = 2 means b / a = .5.
8. And, to find the value for a pair of nodes like a / c, it's just another way of saying "find the route between the nodes and multiply the weights along the way and return it", neat!
9. And how do we solve it? You might have already guessed it, DFS!
10. The code should be easy to understand now.
11. So sometimes, the easiest way to solve a problem is to try to convert it into some we already know. Once you do that, it's a piece of cake.
12. Thanks for reading!

Solution

Javascript

const calcEquation = function(equations, values, queries) {
  const graph = {}, visited = new Set();
  for (let i = 0; i < values.length; i += 1) {
    const [x, y] = equations[i];
    if (!graph[x]) graph[x] = {};
    graph[x][y] = values[i];
    if (!graph[y]) graph[y] = {};
    graph[y][x] = 1 / values[i];
  }
  return queries.map(([x, y]) => dfs(x, y));

  function dfs(x, y) {
    if (!graph[x]) return -1;
    if (graph[x][y]) return graph[x][y];
    for (const key of Object.keys(graph[x])) {
      if (!visited.has(key)) {
        visited.add(key);
        const v = dfs(key, y);
        visited.delete(key);
        if (v !== -1) return graph[x][key] * v;
      }
    }
    return -1;
  }
};

References

1. DFS