Question

Formatted question description: https://leetcode.ca/all/399.html

 399	Evaluate Division

 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.

 @tag-graph

Algorithm

Need a HashSet to record the expressions that have been visited, and then call a recursive function on it.

In the recursive function, we quickly find the expression in the HashMap,

If it is equal to a known expression, return the result directly.
If not, then we need to look for it indirectly. We traverse the known conditions in the HashMap that are the same as the numerator in the analytic formula, skip the ones that have been traversed before, or add the visited array, and then call the recursive function.
- If the return value is a positive number, it will be multiplied by the value of the current known condition and returned, similar to the case 1 above. After the multiplication, b will be eliminated.
- If it is known that no solution is found, -1 will be returned at the end

Code

Java

import java.util.*;

public class Evaluate_Division {

    class Solution {
        public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {

            Map<String, Map<String, Double>> graph = buildGraph(equations, values);

            double[] result = new double[queries.size()];

            for (int i = 0; i < queries.size(); i++) {
                String start = queries.get(i).get(0);
                String end = queries.get(i).get(1);

                Set<String> visited = new HashSet<>();
                result[i] = calculate(graph, start, end, visited);
            }

            return result;
        }

        private double calculate(Map<String, Map<String, Double>> graph, String start, String end, Set<String> visited) {

            if (!graph.containsKey(start) || !graph.containsKey(end)) {
                return -1.0;
            }

            // stop here
            if (graph.get(start).containsKey(end)) {
                return graph.get(start).get(end);
            }

            if (start.equals(end)) {
                return 1.0;
            }

            // start dfs
            visited.add(start); // @note: no need to visited.remove() after recursion

            Map<String, Double> nextSearch = graph.get(start);
            for (Map.Entry<String, Double> entry: nextSearch.entrySet()) {

                String newStart = entry.getKey();
                double factor = entry.getValue();

                if (!visited.contains(newStart)) {
                    double dfsResult = calculate(graph, newStart, end, visited);
                    if (dfsResult > 0) {
                        return factor * dfsResult;
                    }
                }
            }

            visited.remove(start); // restore
            return -1.0;
        }

        private Map<String, Map<String, Double>> buildGraph(List<List<String>> equations, double[] values) {

            // a => (b=>2.0)
            Map<String, Map<String, Double>> graph = new HashMap<>();

            for (int i = 0; i < values.length; i++) {
                List<String> equation = equations.get(i);
                String node1 = equation.get(0);
                String node2 = equation.get(1);

                graph.putIfAbsent(node1, new HashMap<String, Double>());
                graph.putIfAbsent(node2, new HashMap<String, Double>());

                graph.get(node1).put(node2, values[i]);
                graph.get(node2).put(node1, 1.0 / values[i]); // possible bug, value is 0
            }

            return graph;
        }

    }
}

// OJ: https://leetcode.com/problems/evaluate-division/
class Solution {
private:
    unordered_map<string, unordered_map<string, double>> m;
    double dfs(string from, string to, set<string> &visited) {
        if (m[from].count(to)) return m[from][to];
        for (auto p : m[from]) {
            if (visited.count(p.first)) continue;
            visited.insert(p.first);
            double v = dfs(p.first, to, visited);
            if (v != -1) return p.second * v;
        }
        return -1;
    }
public:
    vector<double> calcEquation(vector<vector<string>> &equations, vector<double>& values, vector<vector<string>> queries) {
        for (int i = 0; i < equations.size(); ++i) {
            auto &e = equations[i];
            m[e[0]][e[1]] = values[i];
            m[e[1]][e[0]] = 1 / values[i];
        }
        vector<double> ans;
        for (auto q : queries) {
            set<string> visited;
            auto &a = q[0], &b = q[1];
            if (!m.count(a) || !m.count(b)) ans.push_back(-1);
            else if (a == b) ans.push_back(1);
            else ans.push_back(dfs(a, b, visited));
        }
        return ans;
    }
};

from collections import deque


class Graph(object):
  def __init__(self):
    self.graph = {}

  def get(self, label):
    if label not in self.graph:
      self.graph[label] = GraphNode(label)
    return self.graph[label]

  def query(self, node1, node2):
    g = self.graph
    if len(node1.nbrs) == 0 or len(node2.nbrs) == 0:
      return -1.0
    if node1 == node2:
      return 1.0
    queue = deque([(node1, 1)])
    visited = set([node1.label])
    while queue:
      node, ans = queue.popleft()
      for nbr in node.nbrs:
        if nbr not in visited:
          w = node.nbrs[nbr]
          visited |= {nbr}
          nbrNode = g.get(nbr)
          if nbrNode == node2:
            return ans * w
          queue.append((nbrNode, ans * w))

    return -1.0

  def connect(self, node1, node2, div):
    node1.nbrs[node2.label] = div
    if div != 0:
      node2.nbrs[node1.label] = 1.0 / div
    else:
      node2.nbrs[node1.label] = float("inf")


class GraphNode(object):
  def __init__(self, label):
    self.label = label
    self.nbrs = {}


class Solution(object):
  def calcEquation(self, equations, values, queries):
    """
    :type equations: List[List[str]]
    :type values: List[float]
    :type queries: List[List[str]]
    :rtype: List[float]
    """
    visited = {}
    g = Graph()
    ans = []
    for i in range(0, len(equations)):
      label1, label2 = equations[i]
      node1, node2 = g.get(label1), g.get(label2)
      g.connect(node1, node2, values[i])

    for query in queries:
      ans.append(g.query(g.get(query[0]), g.get(query[1])))
    return ans

399 - Evaluate Division

Question

Algorithm

Code

All Problems

All Solutions