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

coding problems