Java DFS, 4ms, single nested HashMap, 52 lines of code


  • 0
    S

    I was not able to see use graph to solve in the beginning because I failed to see the relationships and I am not familiar with the math behind this problem. After see some solutions, I made this answer my own. The idea is to search any path from symbol A to symbol B (DFS will do). The values to the vertices are ratios. When traversal the graph, multiply the rations you encountered as the result.

    Hope it helps

        public void addEdge(String sa, String sb, double val, Map<String, Map<String, Double>> graph) {
            Map<String, Double> vertex = graph.get(sa);
            if (vertex == null) {
                vertex = new HashMap<>();
                graph.put(sa, vertex);
            }
            vertex.put(sb, val);
        }
    
        public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
    
            Map<String, Map<String, Double>> graph = new HashMap<>();
    
            for (int i  = 0; i < values.length; i++) {
                String[] syms = equations[i];
                String sym1 = syms[0];
                String sym2 = syms[1];
                addEdge(sym1, sym2, values[i], graph);
                addEdge(sym2, sym1, 1 / values[i], graph);
            }
    
    
            double[] rt = new double[queries.length];
            for (int i = 0;i < queries.length; i++) {
                String[] syms = queries[i];
                String sym1 = syms[0];
                String sym2 = syms[1];
                rt[i] = countRatio(graph, sym1, sym2, new HashSet<>());
            }
            return rt;
        }
    
        private double countRatio(Map<String, Map<String, Double>> graph, String syma, String symb, Set<String> visited) {
            Map<String, Double> vertex = graph.get(syma);
            visited.add(syma);
            if (vertex == null) return -1;
            if (syma.equals(symb)) return 1;
            for (Map.Entry<String, Double> e : vertex.entrySet()) {
                String sb = e.getKey();
                Double ratio = e.getValue();
                if (!visited.contains(sb)) {
                    double cr = countRatio(graph, sb, symb, visited);
                    if (cr != -1) {
                        double res = ratio * cr;
                        if (visited.contains(symb)) return res;   
                    }
                }
            }
            return -1;
        }

Log in to reply
 

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