Use graph to solve the problem with explanation


  • 0
    E
    public class Solution {
        
        /**
         * Use graph to solve the question
         * 
         * Mode:
         * The node of the graph is the string, the edge is the value
         * For Example: a / b = 2.0, then we have two nodes: 'a', 'b'. the two edges between 'a' and 'b'
         *  Edge: a->b is 2.0
         *  Edge: b->a is 1.0/2.0 (0.5)
         * 
         * When we do the query, we just need to do the graph search. I am using BFS here. We travel the tree and multiple the edge value alone the way. then we can find the anser
         * For Exampe:  a/b = 2.0   b/c = 3.0:   
         *      Case 1: Query a/c
         *      a/c = (a/b)*(b/c), That is why we can get the answer multiple the edge value
         *      Case 2: Query c/a
         *      c/a = (c/b)*(b/a). That is the reason we create two edges, now the algorithm is same as case 1. just multiple the edge value
         *      Case 3: can't find the divident in the graph, return -1
         *      Case 4: can't find the divisor in the graph, return -1
         * 
         * */
         
        private class Edge{
            public String s=null;
            public double v=0.0;
            
            public Edge(String s, double v){
                this.s = s;
                this.v = v;
            }
        }
        
        private HashMap<String, List<Edge>> g = new HashMap();
        
        public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
            process(equations, values);
            
            double[] res = new double[queries.length];
            
            for(int i=0; i<queries.length; i++){
                res[i] = find(queries[i][0], queries[i][1]);
            }
            return res;
        }
        /**
         * creat the graph data
         * */
        private void process(String[][] equations, double[] values){
            for(int i=0; i<equations.length; i++){
                
                //creat two edges
                Edge foward = new Edge(equations[i][1], values[i]); 
                Edge backward = new Edge(equations[i][0], 1.0/values[i]);
                
                if(!g.containsKey(equations[i][0])){
                    g.put(equations[i][0], new ArrayList<Edge>());
                }
                if(!g.containsKey(equations[i][1])){
                    g.put(equations[i][1], new ArrayList<Edge>());
                }
                
                g.get(equations[i][0]).add(foward);
                g.get(equations[i][1]).add(backward);
            }
        }
        
        /**
         * Do the BFS to find the answer
         * */
        private double find(String from, String to){
            Queue<String> q = new LinkedList();
            Queue<Double> qv = new LinkedList();
            
            double res = -1.0;
            if(!g.containsKey(from)){
                return res;
            }
            q.add(from);
            qv.add(1.0);
            HashSet<String> visited = new HashSet();
            visited.add(from);
            
            while(!q.isEmpty()){
                String nextS = q.poll();
                double nextV = qv.poll();
                if(nextS.equals(to)){
                    //found 
                    res = nextV;
                    return res;
                }
                
                List<Edge> neighbor = g.get(nextS);
                for(Edge n: neighbor){
                    if(!visited.contains(n.s)){
                        q.add(n.s);
                        qv.add(nextV*n.v);
                        visited.add(n.s);
                    }
                }
            }
            return res;
        }
    }
    

Log in to reply
 

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