Graph Based solution (Java) Search - DFS


  • 0
    R
    1. If the value for A/B is given then that means an edge exists between these 2 nodes in the graph
    2. We know that if A/B is given B/A can be computed and that is why I insert backward edges also.
    3. To check a/a I simply do the check at the beginning of the dfs logic given that the key(node) exists.
    4. You can use the traverse function and the System logs to help you understand the problem more.

    \m/

    public class Solution {
        
        HashSet<String> visited = new HashSet<String>();
        public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
            HashMap<String, ArrayList<Edge>> graph = new HashMap<String, ArrayList<Edge>>();
            
            
            int index = 0;
            for (String[] cur: equations) {
                String a = cur[0];
                String b = cur[1];
                if (a.equals(b))
                    continue;
                double edge1 = values[index];
                double edge2 = 1/edge1;
                
                if (graph.containsKey(a)) {
                    graph.get(a).add(new Edge(b, edge1, a));
                } else {
                    ArrayList<Edge> temp = new ArrayList<Edge>();
                    temp.add(new Edge(b, edge1, a));
                    graph.put(a, temp);
                }
                
                if (graph.containsKey(b)) {
                    graph.get(b).add(new Edge(a, edge2, b));
                } else {
                    ArrayList<Edge> temp = new ArrayList<Edge>();
                    temp.add(new Edge(a, edge2, b));
                    graph.put(b, temp);
                }
                
                index++;
            }
            
            
            
            double[] ans = new double[queries.length];
            
            for (int i = 0; i < queries.length; i++) {
                String[] query = queries[i];
                visited.clear();
               // System.out.println("From " + query[0] + " to " + query[1]);
                ans[i] =  dfs(graph, query[0], query[1], 1);
                
            }
           // traverse(graph);
            //double ans2 = dfs(graph, "a", "c", 1);
            //System.out.println("The answer 2 is " + ans2);
            
            return ans;
            
            
        }
        
        
        public double dfs(HashMap<String, ArrayList<Edge>> graph, String start, String end, double ans) {
            if (start.equals(end) && graph.containsKey(start))
                return ans;
            visited.add(start);
            List<Edge> neighbors = getNeighbors(graph, start);
            
            double result = -1.0;
            if (neighbors.size() > 0) {
                for (Edge e: neighbors) {
                  //  System.out.println("The next is " + e.next + " The end is " + end);
                    if (e.next.equals(end)){
                       // System.out.println("Found!");
                        return result = ans * e.edge;
                     }
                    if (!visited.contains(e.next)) {
                        // carry out dfs again
                        result = dfs(graph, e.next, end, ans * e.edge);
                        if (result != -1)
                            break;
                    }
                }
            }
            
            
            return result;
        }
        
        
        
        public ArrayList<Edge> getNeighbors(HashMap<String, ArrayList<Edge>> graph, String curr) {
            ArrayList<Edge> sol = new ArrayList<Edge>();
            if (graph.containsKey(curr)) {
                sol = graph.get(curr);
            }
            return sol;
        }
        
        
        
        public static void traverse(HashMap<String, ArrayList<Edge>> graph) {
            String output = "";
            System.out.println(graph);
            for (String s : graph.keySet()) {
                output += s + " -> ";
                for (Edge e : graph.get(s)) {
                    output += e.next;
                    output += " ";
                }
                output += "\n";
            }
            
            System.out.println(output);
        }
    }
    
    
    class Edge {
        String next;
        double edge;
        String curr;
        public Edge(String neighbor, double edge, String curr) {
            this.next = neighbor;
            this.edge = edge;
            this.curr = curr;
        }
        
        @Override
        public String toString() {
            return curr + "->" + next;
        }
        
    }
    
    

Log in to reply
 

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