Concise and short Java DFS solution


  • 0
    S
    public class Solution {
        public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
            Map<String, Set<String>> graph = new HashMap<>();
            Map<String, Double> mapValues = new HashMap<>();
            for (int i = 0; i < equations.length; i++) {
                String val1 = equations[i][0], val2 = equations[i][1];
                if (!graph.containsKey(val1)) {
                    graph.put(val1, new HashSet<String>());
                }
                if (!graph.containsKey(val2)) {
                    graph.put(val2, new HashSet<String>());
                }
                graph.get(val1).add(val2);
                graph.get(val2).add(val1);
                mapValues.put(val1 + "/" + val2, values[i]);
                mapValues.put(val2 + "/" + val1, 1 / values[i]);
            }
            int length = queries.length;
            double[] ret = new double[length];
            for (int i = 0; i < length; i++) {
                if (!graph.containsKey(queries[i][0])) {
                    ret[i] = -1;
                } else {
                    ret[i] = DFS(graph, mapValues, queries[i][0], queries[i][1], 1, new HashSet<String>());
                }
            }
            return ret;
        }
        
        public double DFS(Map<String, Set<String>> graph, Map<String, Double> mapValues, String val1, String val2, double prevVal, Set<String> visited) {  
            if (graph.get(val1).contains(val2)) {
                return prevVal * mapValues.get(val1 + "/" + val2);
            }
            for (String key : graph.get(val1)) {
                if (visited.add(key + "/" + val2)) {
                    double curVal = prevVal * mapValues.get(val1 + "/" + key);
                    double res = DFS(graph, mapValues, key, val2, curVal, visited);
                    if (res != -1) {
                        return res;
                    }
                }
            }
            return -1;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.