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] = [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.
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.0 queries 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 <= 20equations[i].length == 21 <= Ai.length, Bi.length <= 5values.length == equations.length0.0 < values[i] <= 20.01 <= queries.length <= 20queries[i].length == 21 <= Cj.length, Dj.length <= 5Ai, Bi, Cj, Djconsist of lower case English letters and digits.
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
