Concise and easy to understand Java solution


  • 0
    L
    public class Solution {
        public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
            Map<String, Map<String, Double>> adj = new HashMap<>();
            Map<String, Boolean> visited = new HashMap<>();
            for (int i = 0; i < equations.length; i++) {
                String v = equations[i][0];
                String w = equations[i][1];
                adj.putIfAbsent(v, new HashMap<>());
                adj.get(v).put(w, values[i]);
                adj.putIfAbsent(w, new HashMap<>());
                adj.get(w).put(v, 1 / values[i]);
                
                visited.putIfAbsent(v, false);
                visited.putIfAbsent(w, false);
            }
            
            double[] res = new double[queries.length];
            int idx = 0;
            for (String[] query : queries) {
                res[idx++] = dfs(adj, query[0], query[1], 1.0, visited);
            }
            return res;
        }
        
        private double dfs(Map<String, Map<String, Double>> adj, String start, String end, double pd, Map<String, Boolean> visited) {
            if (!adj.containsKey(start) || !adj.containsKey(end)) return -1.0;
            if (start.equals(end)) return pd;
            visited.put(start, true);
            Map<String, Double> edges = adj.get(start);
            double res = -1.0;
            for (String v : edges.keySet()) {
                double weight = edges.get(v);
                if (!visited.get(v)) res = Math.max(res, dfs(adj, v, end, pd * weight, visited));
            }
            visited.put(start, false);
            return res;
        }
        
    }
    

Log in to reply
 

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