# Leetcode Evaluate Division problem solution

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:
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;
}

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;

}

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_set<string> bc_{};

double dfs(string origin, string dest) {
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;
}
};
```