EvaluateDivision.java

// https://leetcode.com/problems/evaluate-division
// N = |equations|, M = |queries|
// T: O(N + M*N) = O(MN)
// S: O(N + M)

import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

public class EvaluateDivision {
    public static double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        final Map<String, Map<String, Double>> graph = createGraph(equations, values);
        return computeQueries(graph, queries);
    }

    private static Map<String, Map<String, Double>> createGraph(List<List<String>> equations, double[] values) {
        final Map<String, Map<String, Double>> result = new HashMap<>();
        for (int i = 0 ; i < equations.size() ; i++) {
            final List<String> equation = equations.get(i);
            final String dividend = equation.get(0), divisor = equation.get(1);
            result.putIfAbsent(dividend, new HashMap<>());
            result.putIfAbsent(divisor, new HashMap<>());
            result.get(dividend).put(divisor, values[i]);
            result.get(divisor).put(dividend, 1 / values[i]);
        }
        return result;
    }

    private static double[] computeQueries(Map<String, Map<String, Double>> graph, List<List<String>> queries) {
        final double[] result = new double[queries.size()];
        for (int i = 0 ; i < queries.size() ; i++) {
            final List<String> query = queries.get(i);
            final String dividend = query.get(0), divisor = query.get(1);
            if (!graph.containsKey(dividend) || !graph.containsKey(divisor)) {
                result[i] = -1;
            } else if (dividend.equals(divisor)) {
                result[i] = 1;
            } else {
                result[i] = computeDfs(graph, dividend, divisor);
            }
        }
        return result;
    }

    private static double computeDfs(Map<String, Map<String, Double>> graph, String dividend, String divisor) {
        return dfs(graph, dividend, divisor, 1, new HashSet<>());
    }

    private static double dfs(Map<String, Map<String, Double>> graph, String current, String target, double product, Set<String> visited) {
        if (current.equals(target)) {
            return product;
        }
        if (visited.contains(current)) {
            return -1;
        }
        visited.add(current);
        for (Map.Entry<String, Double> edges : graph.get(current).entrySet()) {
            final double result = dfs(graph, edges.getKey(), target, product * edges.getValue(), visited);
            if (result != -1) {
                return result;
            }
        }
        return -1;
    }
}