Java graph + short explanation


  • 1
    A

    The idea is simple. We will build a graph where vertexes will be the strings and the edges will be the values. If a/b is 2.0 than b/a is equal to 1.0/2.0. So, we will build the graph by using this fact. If we can rich from one vertex to another vertex that means the answer exists otherwise not. The answer will be the multiplication of edge values from start vertex till end vertex;

    public class Solution {
        HashMap<String, ArrayList<Pair>> g = new HashMap<>();
        
        public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
            
            for (int i=0; i<equations.length; i++) {
                String from = equations[i][0];
                String to = equations[i][1];
                double val = values[i];
                g.putIfAbsent(from, new ArrayList<>());
                g.putIfAbsent(to, new ArrayList<>());
                g.get(from).add(new Pair(to, val));
                g.get(to).add(new Pair(from, 1.0/val));
            }
            
            double ans [] = new double[queries.length];
            for (int i=0; i<queries.length; i++) {
                String from = queries[i][0];
                String to = queries[i][1];
                ans[i] = dfs(from, to, 1.0, new HashSet<>());
                if (ans[i]==0.0) ans[i] = -1.0;
            }
            return ans;
        }
        
        private double dfs(String from, String to, double mult, HashSet<String> visited) {
            if (visited.contains(from)) return 0.0;
            if (!g.containsKey(from)) return 0.0;
            if (from.equals(to)) return mult;
            visited.add(from);
    
            double ans = 0.0;
            for (Pair p: g.get(from)) {
                String v = p.to;
                double val = p.val;
                ans = dfs(v, to, mult*val, visited);
                if (ans!=0.0) break;
            }
            
            visited.remove(from);
            return ans;
        }    
        
        class Pair {
            String to;
            double val;
            public Pair (String to, double val) {
                this.to = to;
                this.val = val;
            }
        }
    }
    

Log in to reply
 

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