5ms Easy-to-understand Java Solution


  • 0
    O
    public static class Vertex {
            String name;
            double weight;
            Vertex(String name, double weight) { this.name=name; this.weight=weight; }
        }
    
        public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
            double[] results = new double[queries.length];
            Arrays.fill(results, -1.0);
            Map<String,Set<Vertex>> G = createGraph(equations, values);
            int pos = 0;
            for(String[] query: queries) {
                if (G.containsKey(query[0]) && G.containsKey(query[1])) {
                    calcResult(G, new HashSet<String>(), query[0], query[1], 1.0, results, pos);
                }
                pos++;
            }
            return results;
        }
    
        private boolean calcResult(Map<String,Set<Vertex>> G, Set<String> visited, String src, String dst, double result, double[] finalResult, int finalResultPos) {
            visited.add(src);
            if (src.equals(dst)) {
                finalResult[finalResultPos] = result;
                return true;
            }
            for(Vertex v: G.get(src)) {
                if (!visited.contains(v.name) && calcResult(G,visited,v.name,dst,result*v.weight,finalResult,finalResultPos)) {
                    return true;
                }
            }
            return false;
        }
    
        private Map<String,Set<Vertex>> createGraph(String[][] equations, double[] values) {
            Map<String,Set<Vertex>> G = new HashMap<>();
            for(int i=0; i<values.length; i++) {
                String src = equations[i][0];
                String dst = equations[i][1];
                double weight = values[i];
                double inverseWeight = 1.0/weight;
                if (!G.containsKey(src)) {
                    G.put(src, new HashSet<>());
                }
                if (!G.containsKey(dst)) {
                    G.put(dst, new HashSet<>());
                }
                G.get(src).add(new Vertex(dst,weight));
                G.get(dst).add(new Vertex(src, inverseWeight));
            }
            return G;
        }
    

Log in to reply
 

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