Very Clear JAVA DFS Solution with explanation


  • 0
    T

    //construct a Edge class to store both weight and value
    class Edge {
    double weight;
    String val;
    public Edge(double w, String s){
    this.weight = w;
    this.val = s;
    }
    }

    public class Solution {

    public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
        if (queries.length == 0) {
            return new double[0];
        }
        double[] rst = new double[queries.length];
        HashMap<String, HashSet<Edge>> graph = new HashMap<>();
        //vertices
        for (String[] equ : equations) {
            graph.putIfAbsent(equ[0], new HashSet<Edge>());
            graph.putIfAbsent(equ[1], new HashSet<Edge>());
        }
        //edges
        for (int i = 0; i < values.length; i++) {
            String[] equ = equations[i];
            double weight = values[i];
            graph.get(equ[0]).add(new Edge(weight, equ[1]));
            graph.get(equ[1]).add(new Edge(1 / weight, equ[0]));
        }
        
        for (int i = 0; i < queries.length; i++) {
            String cur = queries[i][0];
            String target = queries[i][1];
            
            if (graph.get(cur) == null || graph.get(target) == null) {//characters not showing up
                rst[i] = -1.0;
            } else if (cur.equals(target)) {//same characters
                rst[i] = 1.0;
            } else {
                double answer = dfs(cur, target, graph, 1, cur);
                rst[i] = answer;
            }
        }
        
        return rst;
    }
    //use a parent to prevent thrashing
    public double dfs(String cur, String target, HashMap<String, HashSet<Edge>> graph, double val, String parent) {
        HashSet<Edge> neighbor = graph.get(cur);
        for (Edge edge : neighbor) {
            if (!edge.val.equals(parent)) {
                val = val * edge.weight;
                if (edge.val.equals(target)) {
                    return val;
                } else {
                    double dfs = dfs(edge.val, target, graph, val, cur);
                    if (dfs != -1) {
                        return dfs;
                    }
                }
                //backtracking
                val = val / edge.weight;
            }
        }
        return -1;
    }
    

    }


Log in to reply
 

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