Java solution using graph with one map.


  • 0
    U
    public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
        
        Map<String, Map<String, Double>> map = new HashMap<>();
        
        double[] res = new double[queries.length];
        
        for (int i =0; i < equations.length; i++) {
            String dividend = equations[i][0];
            String divisor = equations[i][1];
            if (!map.containsKey(dividend)) {
                map.put(dividend, new HashMap<>());
            } 
            if (!map.containsKey(divisor)) {
                map.put(divisor, new HashMap<>());
            }
            map.get(dividend).put(divisor, values[i]);
            map.get(divisor).put(dividend, 1/values[i]);
        }
        for (int i = 0; i < res.length; i++) {
            Set<String> visited = new HashSet<>();
            
            res[i] = dfs(map, visited, queries[i][0], queries[i][0], queries[i][1], 1.0);
        }
        
        return res;
    }
    
    public static double dfs(Map<String, Map<String, Double>> map, Set<String> visited, String cur, String start, String end, double value) {
        
        if(!map.containsKey(cur)) {
            return -1.0;
        }
        if (cur.equals(end)) {
            return value;
        }
        if (visited.contains(cur)) {
            return -1.0;
        }
        
        visited.add(cur);
        Map<String, Double> list = map.get(cur);
        for (Map.Entry<String, Double> entry : list.entrySet()) {
            String next = entry.getKey();
            double curVal = entry.getValue();
            double val = dfs(map, visited, next, start, end, value * curVal);
            if (val != -1.0) {
                return val;
            }
        }
        visited.remove(cur);
        return -1.0;
    }

Log in to reply
 

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