Floyd-Warshall

[some explanation of Floyd-Warshall to be added here]

Apply Floyd-Warshall concept to connect paths

If we don't care about the path length / path length doesn't affect the result (in below problem), the effect of applying Floyd-Warshall algorithm is making disjoint paths connected together.

399. Evaluate Division

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

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

class Solution {
    public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
        Map<String, Map<String, Double>> graph = new HashMap<>();        

        for(int i=0; i<equations.length; i++) {
            Map<String, Double> children = graph.getOrDefault(equations[i][0], new HashMap<String, Double>());
            children.put(equations[i][1], values[i]);
            children.put(equations[i][0], 1.0);
            graph.put(equations[i][0], children);

            children = graph.getOrDefault(equations[i][1], new HashMap<String, Double>());
            children.put(equations[i][0], 1.0/values[i]);
            children.put(equations[i][1], 1.0);
            graph.put(equations[i][1], children);
        }

        for(String k: graph.keySet()) {
            for(String i: graph.get(k).keySet()) {
                for(String j: graph.get(k).keySet()) {
                    graph.get(i).put(j, graph.get(i).get(k)*graph.get(k).get(j));
                }
            }
        }

        double[] result = new double[queries.length];
        for(int i=0; i<queries.length; i++) {
            if(!graph.containsKey(queries[i][0])) result[i] = -1;
            else if(!graph.get(queries[i][0]).containsKey(queries[i][1])) result[i] = -1;
            else result[i] = graph.get(queries[i][0]).get(queries[i][1]);
        }


        return result;
    }
}

But note that Floyd-Warshall is$$O(n^3)$$, in some case, the queries are not that many, DFS will be more efficient.

Technique: use HashSet to mark visited nodes instead of visited[] array.

class Solution {
    public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
        Map<String, Map<String, Double>> graph = new HashMap<>();        

        for(int i=0; i<equations.length; i++) {
            Map<String, Double> children = graph.getOrDefault(equations[i][0], new HashMap<String, Double>());
            children.put(equations[i][1], values[i]);
            graph.put(equations[i][0], children);

            children = graph.getOrDefault(equations[i][1], new HashMap<String, Double>());
            children.put(equations[i][0], 1.0/values[i]);
            graph.put(equations[i][1], children);
        }

        double[] result = new double[queries.length];
        for(int i=0; i<queries.length; i++) {
            result[i] = calDFS(graph, queries[i][0], queries[i][1], new HashSet<String>(), 1.0);
        }

        return result;
    }

    public double calDFS(Map<String, Map<String, Double>> graph, String start, String end, Set<String> path, double value) {
        if(path.contains(start)) return -1;
        if(!graph.containsKey(start)) return -1;
        if(graph.get(start).containsKey(end)) return graph.get(start).get(end)*value;

        //in this problem, we don't need to remove the marking 
        //because if any later visit get into one of these nodes again, it definitely will be 
        //1) a loop again or 2) a dead-end again (the equations are bidirectional)
        path.add(start); 

        Map<String, Double> children = graph.get(start);
        double eqVal = -1;
        for(Map.Entry<String, Double> nextStart: children.entrySet()) {
            eqVal = calDFS(graph, nextStart.getKey(), end, path, value*nextStart.getValue());
            if(eqVal!=-1) 
                return eqVal;
        }

        return eqVal;
    }
}