Table of Contents

# Evaluate Division – LeetCode Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.

You are given an array of variable pairs `equations`

and an array of real numbers `values`

, where `equations[i] = [A`

and _{i}, B_{i}]`values[i]`

represent the equation `A`

. Each _{i} / B_{i} = values[i]`A`

or _{i}`B`

is a string that represents a single variable._{i}

You are also given some `queries`

, where `queries[j] = [C`

represents the _{j}, D_{j}]`j`

query where you must find the answer for ^{th}`C`

._{j} / D_{j} = ?

Return *the answers to all queries*. If a single answer cannot be determined, return `-1.0`

.

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

**Example 1:**

Input:equations = [["a","b"],["b","c"]], values = [2.0,3.0], queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]Output:[6.00000,0.50000,-1.00000,1.00000,-1.00000]Explanation:Given:a / b = 2.0,b / c = 3.0queries are:a / c = ?,b / a = ?,a / e = ?,a / a = ?,x / x = ?return: [6.0, 0.5, -1.0, 1.0, -1.0 ]

**Example 2:**

Input:equations = [["a","b"],["b","c"],["bc","cd"]], values = [1.5,2.5,5.0], queries = [["a","c"],["c","b"],["bc","cd"],["cd","bc"]]Output:[3.75000,0.40000,5.00000,0.20000]

**Example 3:**

Input:equations = [["a","b"]], values = [0.5], queries = [["a","b"],["b","a"],["a","c"],["x","y"]]Output:[0.50000,2.00000,-1.00000,-1.00000]

**Constraints:**

`1 <= equations.length <= 20`

`equations[i].length == 2`

`1 <= A`

_{i}.length, B_{i}.length <= 5`values.length == equations.length`

`0.0 < values[i] <= 20.0`

`1 <= queries.length <= 20`

`queries[i].length == 2`

`1 <= C`

_{j}.length, D_{j}.length <= 5`A`

consist of lower case English letters and digits._{i}, B_{i}, C_{j}, D_{j}

# C++ Evaluate Division LeetCode Solution

```
``````
class Solution {
public:
void dfs(string start,string end,map<string,double>& mp,map<string,vector<string>>& graph,double& val,map<string,int>& visited,bool& found){
visited[start]=1;
if(found==true)
return ;
for(auto child:graph[start]){
if(visited[child]!=1){
// cout<<start<<" "<<child<<"\n";
val*=mp[start+"->"+child];
if(end==child){
// cout<<end<<" -- "<<child<<"\n";
found=true;
return ;
}
dfs(child,end,mp,graph,val,visited,found);
if(found==true){
return ;
}
else{
val/=mp[start+"->"+child];
}
}
}
}
vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
vector<double> ans;
map<string,double> mp;
map<string,vector<string>> graph;
for(int i=0;i<equations.size();i++){
string u=equations[i][0];
string v=equations[i][1];
mp[u+"->"+v]=values[i];
mp[v+"->"+u]=1/values[i];
graph[u].push_back(v);
graph[v].push_back(u);
}
for(int i=0;i<queries.size();i++){
string start=queries[i][0];
string end=queries[i][1];
if(graph.find(start)==graph.end()||graph.find(end)==graph.end()){
ans.push_back(-1);
}
else{
// ans.push_back(1);
double val=1;
map<string,int> visited;
bool found=false;
if(start==end){
found=true;
}
else
dfs(start,end,mp,graph,val,visited,found);
if(found==true)
ans.push_back(val);
else
ans.push_back(-1);
}
}
return ans;
}
};
```

# Java Evaluate Division LeetCode Solution

```
``````
public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
HashMap<String, ArrayList<String>> pairs = new HashMap<String, ArrayList<String>>();
HashMap<String, ArrayList<Double>> valuesPair = new HashMap<String, ArrayList<Double>>();
for (int i = 0; i < equations.length; i++) {
String[] equation = equations[i];
if (!pairs.containsKey(equation[0])) {
pairs.put(equation[0], new ArrayList<String>());
valuesPair.put(equation[0], new ArrayList<Double>());
}
if (!pairs.containsKey(equation[1])) {
pairs.put(equation[1], new ArrayList<String>());
valuesPair.put(equation[1], new ArrayList<Double>());
}
pairs.get(equation[0]).add(equation[1]);
pairs.get(equation[1]).add(equation[0]);
valuesPair.get(equation[0]).add(values[i]);
valuesPair.get(equation[1]).add(1/values[i]);
}
double[] result = new double[queries.length];
for (int i = 0; i < queries.length; i++) {
String[] query = queries[i];
result[i] = dfs(query[0], query[1], pairs, valuesPair, new HashSet<String>(), 1.0);
if (result[i] == 0.0) result[i] = -1.0;
}
return result;
}
private double dfs(String start, String end, HashMap<String, ArrayList<String>> pairs, HashMap<String, ArrayList<Double>> values, HashSet<String> set, double value) {
if (set.contains(start)) return 0.0;
if (!pairs.containsKey(start)) return 0.0;
if (start.equals(end)) return value;
set.add(start);
ArrayList<String> strList = pairs.get(start);
ArrayList<Double> valueList = values.get(start);
double tmp = 0.0;
for (int i = 0; i < strList.size(); i++) {
tmp = dfs(strList.get(i), end, pairs, values, set, value*valueList.get(i));
if (tmp != 0.0) {
break;
}
}
set.remove(start);
return tmp;
}
```

# Python 3 Evaluate Division LeetCode Solution

```
``````
class Solution:
def answer(self, current, end, scalar):
if current==end: return scalar
self.visited.add(current)
if current in self.graph:
for i in self.graph[current]:
if i[0] not in self.visited:
a=self.answer(i[0],end,scalar*i[1])
if a!=-1: return a
return -1
def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
self.graph,self.visited={},set()
for i in range(len(equations)):
if equations[i][0] not in self.graph:
self.graph[equations[i][0]]=[]
if equations[i][1] not in self.graph:
self.graph[equations[i][1]]=[]
self.graph[equations[i][0]].append((equations[i][1],1/values[i]))
self.graph[equations[i][1]].append((equations[i][0],values[i]))
v=[]
for i in queries:
self.visited=set()
if i[0] not in self.graph or i[1] not in self.graph:
v.append(-1)
continue
v.append(1/self.answer(i[0],i[1],1) if i[0]!=i[1] else 1)
return v
```

Array-1180

String-562

Hash Table-412

Dynamic Programming-390

Math-368

Sorting-264

Greedy-257

Depth-First Search-256

Database-215

Breadth-First Search-200

Tree-195

Binary Search-191

Matrix-176

Binary Tree-160

Two Pointers-151

Bit Manipulation-140

Stack-133

Heap (Priority Queue)-117

Design-116

Graph-108

Simulation-103

Prefix Sum-96

Backtracking-92

Counting-86

Sliding Window-73

Linked List-69

Union Find-66

Ordered Set-48

Monotonic Stack-47

Recursion-43

Trie-41

Binary Search Tree-40

Divide and Conquer-40

Enumeration-39

Bitmask-37

Queue-33

Memoization-32

Topological Sort-31

Geometry-30

Segment Tree-27

Game Theory-24

Hash Function-24

Binary Indexed Tree-21

Interactive-18

Data Stream-17

String Matching-17

Rolling Hash-17

Shortest Path-16

Number Theory-16

Combinatorics-15

Randomized-12

Monotonic Queue-9

Iterator-9

Merge Sort-9

Concurrency-9

Doubly-Linked List-8

Brainteaser-8

Probability and Statistics-7

Quickselect-7

Bucket Sort-6

Suffix Array-6

Minimum Spanning Tree-5

Counting Sort-5

Shell-4

Line Sweep-4

Reservoir Sampling-4

Eulerian Circuit-3

Radix Sort-3

Strongly Connected Componen-t2

Rejection Sampling-2

Biconnected Component-1