Java Solution


  • 0
    H
    public class Solution {
        public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
            double[] ans = new double[queries.length];
            Map<String, Map<String, Double>> graph = new HashMap<>();
            for (int i = 0; i < equations.length; i++) {
                String[] e = equations[i];
                graph.putIfAbsent(e[0], new HashMap<>());
                graph.putIfAbsent(e[1], new HashMap<>());
                graph.get(e[0]).put(e[1], values[i]);
                graph.get(e[1]).put(e[0], 1.0/values[i]);
            }
            
            for (int i = 0; i < queries.length; i++) {
                Set<String> visited = new HashSet<>();
                ans[i] = dfs(graph, visited, 1.0, queries[i][0], queries[i][1]);
            }
            return ans;
        }
        private double dfs(Map<String, Map<String, Double>> graph, Set<String> visited, double tmpAns, String from, String to) {
            if (!graph.containsKey(from)) {
                return -1.0;
            }
            if (from.equals(to)) {
                return tmpAns;
            }
            visited.add(from);
            Map<String, Double> next = graph.get(from);
            for (Map.Entry<String, Double> entry : next.entrySet()) {
                if (!visited.contains(entry.getKey())) {
                    double result = dfs(graph, visited, tmpAns * entry.getValue(), entry.getKey(), to);
                    if (result != -1.0) {
                        return result;
                    }
                }
            }
            return -1.0;
        }
    }
    

Log in to reply
 

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