Java DFS soution


  • 0
    D
    public class Solution {
        private Map<String, GraphNode> graph = new HashMap<>();
    
        public double[] calcEquation(String[][] equations, double[] values, String[][] query) {
            assert equations != null && values != null && equations.length == values.length;
            int n = equations.length;
            for (int i = 0; i < n; i++) {
                GraphNode fromNode = getNode(equations[i][0]);
                GraphNode toNode = getNode(equations[i][1]);
                fromNode.children.add(new Edge(values[i], toNode));
                toNode.children.add(new Edge(1.0 / values[i], fromNode));
            }
            assert query != null;
            int m = query.length;
            double[] ret = new double[m];
            for (int i = 0; i < m; i++) {
                ret[i] = calc(query[i]);
            }
            return ret;
        }
    
        private double calc(String[] query) {
            Tuple tuple = dfs(query[0], query[1], new HashSet<String>(), 1.0);
            return tuple.found ? tuple.val : -1.0;
        }
    
        private Tuple dfs(String nodeName, String target, Set<String> visited, double val) {
            if (!graph.containsKey(nodeName) || visited.contains(nodeName)) {
                return new Tuple(false, -1.0);
            }
            visited.add(nodeName);
            if (nodeName.equals(target)) {
                return new Tuple(true, val);
            }
            for (Edge child : getNode(nodeName).children) {
                Tuple candidate = dfs(child.target.str, target, visited, val * child.val);
                if (candidate.found) {
                    return new Tuple(true, candidate.val);
                }
            }
            return new Tuple(false, -1.0);
        }
    
        private GraphNode getNode(String str) {
            if (!graph.containsKey(str)) {
                graph.put(str, new GraphNode(str));
            }
            return graph.get(str);
        }
    
        class GraphNode {
            String str;
            List<Edge> children = new ArrayList<>();
            public GraphNode(String str) {
                this.str = str;
            }
        }
    
        class Edge {
            double val;
            GraphNode target;
            public Edge(double val, GraphNode target) {
                this.val = val;
                this.target = target;
            }
        }
    
        class Tuple {
            boolean found;
            double val;
            public Tuple(boolean found, double val) {
                this.found = found;
                this.val = val;
            }
        }
    }
    

Log in to reply
 

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