[java/4ms] neat code, DFS, easy to understand


  • 0
    private double dfs(HashMap<String, HashMap<String, Double>> graph, String start, String end, Set<String> keys) {
            // start doesn't exist
            HashMap<String, Double> next = graph.get(start);
            if (next == null) return -1.0;
            // the start node exist
            if (start.equals(end)) return 1.0;
    
            double res;
            for (Map.Entry<String, Double> entry : next.entrySet()) {
                String key = entry.getKey();
                if (keys.add(key)) {
                    res = entry.getValue() * dfs(graph, key, end, keys);
                    keys.remove(key);
                    if (res > 0) return res;
                }
            }
            
            return -1.0;
        }
        
        public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
            HashMap<String, HashMap<String, Double>> graph = new HashMap<>();
            int i = 0;
            for (String[] eq : equations) {
                // build undirected graph
                if (graph.containsKey(eq[0])) {
                    graph.get(eq[0]).put(eq[1], values[i]);
                } else {
                    HashMap<String, Double> tmp = new HashMap<>();
                    graph.put(eq[0], tmp);
                    tmp.put(eq[1], values[i]);
                }
                
                if (graph.containsKey(eq[1])) {
                    graph.get(eq[1]).put(eq[0], 1 / values[i]);
                } else {
                    HashMap<String, Double> tmp = new HashMap<>();
                    graph.put(eq[1], tmp);
                    tmp.put(eq[0], 1 / values[i]);
                }
                i++;
            }
    
            double[] res = new double[queries.length];
            for (int j = 0; j < queries.length; j++) {
                res[j] = dfs(graph, queries[j][0], queries[j][1], new HashSet<>());
            }
            return res;
        }
    

Log in to reply
 

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