399. Evaluate Division

// LeetCode URL: https://leetcode.com/problems/evaluate-division/
import java.util.HashMap;
import java.util.HashSet;

/**
 * Build a graph of equations and then perform DFS to find the result of each
 * query
 *
 * Imagine a/b = k as a link between node a and b, the value of link from a to b
 * is k, the reverse link is 1/k. Query is to find a path between two nodes.
 *
 * Time Complexity: BuildGraph + DFS * NoOfQueries. BuildGraph = O(E). DFS =
 * (NoOfNodes + NoOfEdges) = O(2*E + 2*E) = O(4*E).
 *
 * Thus total complexity = O(E + 4*E*Q) = O(E*Q).
 *
 * Space Complexity: Space taken by graph + Recursion Depth = O(E).
 *
 * E = length of equations or values. Q = length of queries
 */
class Solution {
    public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
        if (queries == null || queries.length == 0) {
            return new double[0];
        }

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

        double[] result = new double[queries.length];

        for (int i = 0; i < queries.length; i++) {
            String[] q = queries[i];
            if (!graph.containsKey(q[0]) || !graph.containsKey(q[1])) {
                result[i] = -1.0;
            } else {
                result[i] = dfsHelper(q[0], q[1], new HashSet<>(), graph, 1.0);
            }
        }

        return result;
    }

    private double dfsHelper(String src, String dest, HashSet<String> visited,
            HashMap<String, HashMap<String, Double>> graph, double curVal) {
        if (visited.contains(src)) {
            return -1.0;
        }
        if (src.equals(dest)) {
            return curVal;
        }

        visited.add(src);
        HashMap<String, Double> neighbours = graph.get(src);

        for (String neigh : neighbours.keySet()) {
            double tmp = dfsHelper(neigh, dest, visited, graph, neighbours.get(neigh) * curVal);
            if (tmp != -1.0) {
                return tmp;
            }
        }

        return -1.0;
    }

    private void buildGraph(HashMap<String, HashMap<String, Double>> graph, String[][] equations, double[] values) {
        if (equations == null || equations.length == 0 || values == null || values.length == 0
                || equations.length != values.length) {
            return;
        }

        for (int i = 0; i < equations.length; i++) {
            String[] eq = equations[i];

            if (!graph.containsKey(eq[0])) {
                graph.put(eq[0], new HashMap<>());
            }
            if (!graph.containsKey(eq[1])) {
                graph.put(eq[1], new HashMap<>());
            }

            graph.get(eq[0]).put(eq[1], values[i]);
            graph.get(eq[1]).put(eq[0], 1 / values[i]);
        }
    }
}