46. 399. Evaluate Division

class Solution {
    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        double [] ans = new double[queries.size()];
        Map<String,Map<String,Double>>equationMap = new HashMap<>();

        //constructing the equation map
        for(int i=0;i<equations.size();i++){
            List<String> equation = equations.get(i);
            String a = equation.get(0);
            String b = equation.get(1);

            equationMap.putIfAbsent(a,new HashMap<>());
            equationMap.putIfAbsent(b,new HashMap<>());
            equationMap.get(a).put(b,values[i]);
            equationMap.get(b).put(a,1/values[i]);
        }

        //solve the query
        for(int i=0;i<queries.size();i++){
            List<String>query = queries.get(i);
            String src= query.get(0);
            String target = query.get(1);
            //traverse for the solution
            ans[i] = dfs(equationMap,src,target,new HashSet<>(),1.0);
        }
        return ans;
        
    }

    private double dfs(Map<String,Map<String,Double>>equationMap,String src,String target,HashSet<String>visited,double weight){
        if(!equationMap.containsKey(src)|| !equationMap.containsKey(target)){
            return -1;
        }

        //if src and taget is same - we find our soltuion
        if(src.equals(target)){
            return weight;
        }

        visited.add(src);
        double res=-1.0;

        //connected equation map
        Map<String,Double> connected = equationMap.get(src);
        for(Map.Entry<String,Double> entry : connected.entrySet()){
            String neighbour = entry.getKey();
            if(!visited.contains(neighbour)){
                res= dfs(equationMap,neighbour,target,visited,weight*entry.getValue());
                //if ans found then we will back
                if(res!=-1)
                break;
            }
        }

        visited.remove(src);
        return res;
    }
}