# 399. Evaluate Division ## DFS see in DFS ```java class Solution { class Data { String node; double value; Data(String node, double value) { this.node = node; this.value = value; } } public double[] calcEquation(List> equations, double[] values, List> queries) { Map> graph = buildGraph(equations, values); double[] result = new double[queries.size()]; for (int i = 0 ; i < queries.size(); i++) { List querie = queries.get(i); String start = querie.get(0); String end = querie.get(1); Set visited = new HashSet<>(); visited.add(start); result[i] = dfs(graph, start, end, visited); } return result; } private double dfs(Map> graph, String start, String end, Set visited) { if (graph.get(start) == null || graph.get(end) == null) { // terminal condition return -1; } // terminal condition, at last to == end, so return 1, then bottom up to cal result 1*...value*value... if (start.equals(end)) { return 1; } for (Data child : graph.get(start)) { String to = child.node; double value = child.value; if (visited.contains(to)) { continue; } visited.add(to); double temp = dfs(graph, to, end, visited); visited.remove(to); if (temp != -1) { return temp*value; } } return -1; } private Map> buildGraph(List> equations, double[] values) { Map> map = new HashMap<>(); for (int i = 0; i < equations.size(); i++) { List equation = equations.get(i); String from = equation.get(0); String to = equation.get(1); map.putIfAbsent(from, new ArrayList<>()); map.get(from).add(new Data(to, values[i])); map.putIfAbsent(to, new ArrayList<>()); map.get(to).add(new Data(from, 1.0/values[i])); } return map; } } /* Given: a / b = 2.0, b / c = 3.0 queries are: a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ? return: [6.0, 0.5, -1.0, 1.0, -1.0 ] query c/d a = 2b b = 3c 2 3 a - b - c a/c = 6 b/a = 1/2 a/e = -1 (can't find one of them in graph, return -1) a/a = 1 (can find in graph) x/x = -1 (can't find one of them in graph, return -1) If a single answer cannot be determined, return -1.0. ex: a/e a/b = 1.5 b/c = 2.5 => b = 2.5c => bc = 2.5c/d = 5 => c/d = 2 bc/cd = 5 1.5 2.5 2 a - b - c - d a/c = 1.5*2.5 = c/b = 1/2.5 bc/cd = b/d = 5 cd/bc = d/b = 1/5 */ ``` ## BFS T: O(q\*n), q: queries times, n: graph nodes number S: O(n) ```java class Solution { class Data { String node; double value; Data(String node, double value) { this.node = node; this.value = value; } } public double[] calcEquation(List> equations, double[] values, List> queries) { Map> graph = buildGraph(equations, values); double[] result = new double[queries.size()]; for (int i = 0 ; i < queries.size(); i++) { List querie = queries.get(i); String start = querie.get(0); String end = querie.get(1); //System.out.println("query -> start:" + start + ",end:" + end); result[i] = bfs(graph, start, end); } return result; } private double bfs(Map> graph, String start, String end) { // eliminate duplicate if (!graph.containsKey(start) || !graph.containsKey(end)) { return -1.0; } if (start.equals(end)) { return 1.0; } Queue queue = new LinkedList<>(); queue.offer(new Data(start, 1.0)); Set visited = new HashSet<>(); visited.add(start); while (!queue.isEmpty()) { Data cur = queue.poll(); String from = cur.node; double fromValue = cur.value; for (Data child : graph.get(from)) { String to = child.node; double value = child.value; if (visited.contains(to)) { continue; } //System.out.println("cur:" + cur + ",to:" + to + ",value:" + value); double result = fromValue*value; queue.offer(new Data(to, result)); visited.add(to); if (end.equals(to)) { //System.out.println("cur:" + cur + ", to:" + to + ",end:" + end); return result; } } } return -1.0; } private Map> buildGraph(List> equations, double[] values) { Map> map = new HashMap<>(); for (int i = 0; i < equations.size(); i++) { List equation = equations.get(i); String from = equation.get(0); String to = equation.get(1); map.putIfAbsent(from, new ArrayList<>()); map.get(from).add(new Data(to, values[i])); map.putIfAbsent(to, new ArrayList<>()); map.get(to).add(new Data(from, 1.0/values[i])); } return map; } } /* Given: a / b = 2.0, b / c = 3.0 queries are: a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ? return: [6.0, 0.5, -1.0, 1.0, -1.0 ] query c/d a = 2b b = 3c 2 3 a - b - c a/c = 6 b/a = 1/2 a/e = -1 (can't find one of them in graph, return -1) a/a = 1 (can find in graph) x/x = -1 (can't find one of them in graph, return -1) If a single answer cannot be determined, return -1.0. ex: a/e a/b = 1.5 b/c = 2.5 => b = 2.5c => bc = 2.5c/d = 5 => c/d = 2 bc/cd = 5 1.5 2.5 2 a - b - c - d a/c = 1.5*2.5 = c/b = 1/2.5 bc/cd = b/d = 5 cd/bc = d/b = 1/5 */ ``` --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://timmybeeflin.gitbook.io/cracking-leetcode/dfs-and-bfs/bfs/399.-evaluate-division.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.