In this Leetcode Evaluate Division problem solution you are given an array of variable pairs equations and an array of real numbers values, where equations[i] = [Ai, Bi] and values[i] represent the equation Ai / Bi = values[i]. Each Ai or Bi is a string that represents a single variable.
You are also given some queries, where queries[j] = [Cj, Dj] represents the jth query where you must find the answer for Cj / Dj = ?. Return the answers to all queries. If a single answer cannot be determined, return -1.0.
Problem solution in Python.
class Solution(object): def calcEquation(self, equations, values, queries): """ :type equations: List[List[str]] :type values: List[float] :type queries: List[List[str]] :rtype: List[float] """ dic = {} for i,e in enumerate(equations): if not e[0] in dic:dic[e[0]]={} if not e[1] in dic:dic[e[1]]={} dic[e[0]][e[1]] = values[i] dic[e[1]][e[0]] = 1/values[i] res = [] for q in queries: start = q[0] target = q[1] res.append(self.dfs(start,target,dic,1,set())) return res def dfs(self,start,target,dic,tmp,visited): if not start in dic or not target in dic:return -1 if start==target:return tmp for child in dic[start]: if not (start,child) in visited: visited.add((start,child)) coco = self.dfs(child,target,dic,tmp*dic[start][child],visited) if coco!=-1:return coco visited.remove((start,child)) return -1
Problem solution in Java.
class Solution { public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) { Map<String,Map<String, Double>> map = new HashMap<>(); for(int i=0;i<equations.size();i++){ List<String> list = equations.get(i); String a = list.get(0); String b = list.get(1); if(map.containsKey(a)==false){ map.put(a, new HashMap<>()); } map.get(a).put(b, values[i]); if(map.containsKey(b)==false){ map.put(b, new HashMap<>()); } map.get(b).put(a, 1/values[i]); } int index = 0; double[] res = new double[queries.size()]; for(List<String> ele: queries){ if(map.containsKey(ele.get(0))==false || map.containsKey(ele.get(1))==false){ res[index++] = -1; continue; } double temp = dfs(map, new HashSet<>(), ele.get(0), ele.get(1)); res[index++] = (temp==0?-1:temp); } return res; } public double dfs(Map<String, Map<String, Double>> map, Set<String> seen, String start, String end){ if(start.equals(end)){ return 1; } if(seen.contains(start)){ return 0; } seen.add(start); for(String next: map.get(start).keySet()){ double temp = dfs(map, seen, next, end); if(temp!=0){ return temp*map.get(start).get(next); } } seen.remove(start); return 0; } }
Problem solution in C++.
class Solution { public: vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) { for(int i = 0; i < equations.size(); i++) { string o = equations[i][0]; string d = equations[i][1]; double w = values[i]; double w_reciprocal = 1/w; adj_[o].emplace(d, w); adj_[d].emplace(o, w_reciprocal); } vector<double> res{}; for(const auto &q : queries) { bc_.clear(); string origin = q[0]; string dest = q[1]; res.emplace_back(dfs(origin, dest)); } return res; } private: unordered_map<string, unordered_map<string, double>> adj_{}; unordered_set<string> bc_{}; double dfs(string origin, string dest) { if(adj_.find(origin) == adj_.end()) { return -1; } if(origin == dest) { return 1; } if(bc_.find(origin) != bc_.end()) { return -1; } bc_.emplace(origin); for(const auto &p : adj_[origin]) { string next = p.first; double weight = p.second; double res = dfs(next, dest); if(res != -1) { return res * weight; } } return -1; } };