399. Evaluate Division

https://leetcode.com/problems/evaluate-division/

Equations are given in the format A / B = k, where A and B are variables represented as strings, and k is a real number (floating point number). Given some queries, return the answers. If the answer does not exist, return -1.0.

Example:
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 ].

The input is: vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries , where equations.size() == values.size(), and the values are positive. This represents the equations. Return vector<double>.

According to the example above:

equations = [ ["a", "b"], ["b", "c"] ],
values = [2.0, 3.0],
queries = [ ["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"] ]. 

 

The input is always valid. You may assume that evaluating the queries will result in no division by zero and there is no contradiction.

---

	class Solution {
	public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
	HashMap<String, Map<String, Double>> graph = new HashMap<String, Map<String, Double>>();
	buildGraph(equations, values, graph);
	double[] ans = new double[queries.size()];
	for (int i = 0; i < queries.size(); i++) {
	List<String> q = queries.get(i);
	String num = q.get(0);
	String denom = q.get(1);
	if (!graph.containsKey(num) || !graph.containsKey(denom)) {
	ans[i] = -1.0;
	} else if (num.equals(denom)) {
	ans[i] = 1.0;
	} else {
	Set<String> visited = new HashSet<String>();
	visited.add(num);
	Double result = dfs(num, denom, 1.0, visited, graph);
	ans[i] = result == null ? -1 : result;
	}
	}
	return ans;
	}
	private Double dfs(String num, String denom, Double prefix, Set<String> visited, Map<String, Map<String, Double>> graph) {
	Double ans = null;
	// Invalid, terminate DFS
	if (!graph.containsKey(num)) {
	return ans;
	}
	// Found match
	if (graph.get(num).containsKey(denom)) {
	return prefix * graph.get(num).get(denom);
	}
	for (String neighbor: graph.get(num).keySet()) {
	if (!visited.contains(neighbor)) {
	visited.add(neighbor);
	ans = dfs(neighbor, denom, prefix * graph.get(num).get(neighbor), visited, graph);
	if (ans != null) {
	return ans;
	}
	// backtrack
	visited.remove(neighbor);
	}
	}
	return ans;
	}
	private void buildGraph(List<List<String>> equations, double[] values, Map<String, Map<String, Double>> graph) {
	for (int i = 0; i < equations.size(); i++) {
	String num = equations.get(i).get(0);
	String denom = equations.get(i).get(1);
	graph.putIfAbsent(num, new HashMap<String, Double>());
	graph.putIfAbsent(denom, new HashMap<String, Double>());
	// Build bi directional graph
	graph.get(num).put(denom, values[i]);
	graph.get(denom).put(num, 1.0 / values[i]);
	}
	}
	}

view raw 399.EvaluateDivision.java hosted with ❤ by GitHub