Sexy java solution


  • 0
    Z

    public class Solution {

    public class E {
        String var;
        double val;
        
        public E(String var, double val) {
            this.var = var;
            this.val = val;
        }
    }
    
    public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
        int n = values.length , i, q = queries.length;
        double[] ans = new double[q];
        
        Map<String , List<E>> graph = new HashMap<>();
        
        String a,b;double val;
        
        for(i=0;i<n;i++) {
            a = equations[i][0];
            b = equations[i][1];
            
            val = values[i];
            
            List<E> edges = graph.get(a);
            
            if(edges == null) 
                edges = new ArrayList<>();
            edges.add(new E(b , val));
            
            graph.put(a , edges);
            
            edges = graph.get(b);
            
            if(edges == null) 
                edges = new ArrayList<>();
            edges.add(new E(a , ((double)1)/val));
            
            graph.put(b , edges);
        }
        
        // bfs to get all distance
        Map<String , Map<String , Double>> bfsMap = new HashMap<>();
        
        for(String var : graph.keySet()) {
            bfs(var, graph, bfsMap);
        }
        
        for(i=0;i<q;i++) {
            a = queries[i][0];
            b = queries[i][1];
            
            Map<String , Double> map = bfsMap.get(a);
            
            if(map == null) {
                ans[i] = -1.0;
            } else {
                Double result = map.get(b);
                
                if(result == null) {
                    ans[i] = -1.0; 
                } else {
                    ans[i] = result;
                }
            }
        }
        
        return ans;
    }
    
    class S {
        String var;
        double cur;
        
        public S (String var, double cur) {
            this.var = var;
            this.cur = cur;
        }
    }
    
    public void bfs(String var, Map<String , List<E>> graph, Map<String , Map<String , Double>> bfsMap) {
        Map<String , Double> result = new HashMap<>();
        Queue<S> q = new LinkedList<>();
        Set<String> visited = new HashSet<>();
        
        q.add(new S(var , 1));
        String v; S s;
        double cur;
        
        while(!q.isEmpty()) {
           s = q.poll();
           v = s.var;cur = s.cur;
           
           visited.add(v);
           result.put(v , cur);
           
           List<E> edges = graph.get(v);
           
           for(E edge : edges) {
               if(!visited.contains(edge.var)) {
                   q.add(new S(edge.var , cur * edge.val));
               }
           }
        }
        
        bfsMap.put(var , result);
    }
    

    }


Log in to reply
 

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