Java AC solution using BFS + prev path map


  • 0
    X
        public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {       
            if(queries == null || queries.length == 0 || queries[0].length == 0) return new double[0];        
            Map<String, Map<String, Double>> mapNeighbors = new HashMap<>();        
            for(int i = 0; i < equations.length; i++) {
                if(! mapNeighbors.containsKey(equations[i][0])) {
                    mapNeighbors.put(equations[i][0], new HashMap<String, Double>());
                    mapNeighbors.get(equations[i][0]).put(equations[i][0], 1.0);
                }
                if(! mapNeighbors.containsKey(equations[i][1])) {
                    mapNeighbors.put(equations[i][1], new HashMap<String, Double>());
                    mapNeighbors.get(equations[i][1]).put(equations[i][1], 1.0);
                }            
                mapNeighbors.get(equations[i][0]).put(equations[i][1], values[i]);
                mapNeighbors.get(equations[i][1]).put(equations[i][0], 1.0 / values[i]);
            }
            
            double[] results = new double[queries.length];
            
            for(int i = 0; i < queries.length; i ++) {      
                results[i] = -1.0;
                
                Set<String> visited = new HashSet<>();
                Map<String, String> prev = new HashMap<>(); // path backtrack map        
                Queue<String> q = new LinkedList<>();  // BFS
                q.offer(queries[i][0]);
                
                while(! q.isEmpty()) {
                    String curr = q.poll();
                    if(!mapNeighbors.containsKey(curr)) break;
                    for(String ne : mapNeighbors.get(curr).keySet()) {
                        if(! visited.contains(ne)) {
                            q.offer(ne);
                            visited.add(ne);
                            prev.put(ne, curr);
                            if(ne.equals(queries[i][1])) {                        
                                double r = 1.0;
                                String end = queries[i][1];
                                while(! end.equals(queries[i][0])) {
                                    r *= mapNeighbors.get(prev.get(end)).get(end);
                                    end = prev.get(end);
                                }
                                results[i] = r;
                                q.clear();
                                break;
                            }
                        }
                    }            
                }
            }                
            return results;
        }
    

Log in to reply
 

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