399 Evaluate Division

https://leetcode.com/problems/evaluate-division/submissions/

class Solution {
    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        Map<String, Map<String, Double>> graph = new HashMap<>();
        buildGraph(graph, equations, values);
        double[] ans = new double[queries.size()];
        int idx = 0;
        for (List<String> query : queries) {
            ans[idx] = -1;
            dfs(query.get(0), query.get(1), graph, 1, ans, idx, new HashSet<>());
            idx++;
        }
        return ans;
    }
    private void dfs(String from, String to, 
                    Map<String, Map<String, Double>> graph,
                    double value, double[] ans, int idx, Set<String> visited) {
        if (from.equals(to) && graph.containsKey(from) && graph.containsKey(to)) {
            ans[idx] = value;
            return;
        }
        if (visited.contains(from)) return;
        visited.add(from);
        Map<String, Double> next = graph.get(from);
        if (next == null) return;
        for (Map.Entry<String, Double> entry : next.entrySet()) {
            dfs(entry.getKey(), to, graph, value * entry.getValue(), ans, idx, visited);
        }
    }
    private void buildGraph(Map<String, Map<String, Double>> graph, 
                            List<List<String>> equations, 
                           double[] values) {
        int idx = 0;
        for (List<String> equation : equations) {
            double value = values[idx++];
            Map<String, Double> map = graph.get(equation.get(0));
            if (map == null) map = new HashMap<>();
            map.put(equation.get(1), value);
            graph.put(equation.get(0), map);
            
            map = graph.get(equation.get(1));
            if (map == null) map = new HashMap<>();
            map.put(equation.get(0), 1/value);
            graph.put(equation.get(1), map);
        }
    }
}

很有意思的一道题，也是我第一次mock被问到的题，关键是要记得用visited去重，毕竟可能找不到解，以及记录这个带边权图的方法：用一个map of map，map里是node tag -> map<node tage -> edge val>