Easy to understand DFS solution in Java


  • 0
    M
    public class Solution {
        public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
            Map<String,Map<String,Double>> map = new HashMap<String,Map<String,Double>>();
            for(int i = 0; i < equations.length; i++){
                // equations[i] = ["a","b"]
                if(map.containsKey(equations[i][0])){
                    map.get(equations[i][0]).put(equations[i][1],values[i]);
                }else{
                    Map<String,Double> tmp1 = new HashMap<String,Double>();
                    tmp1.put(equations[i][1],values[i]);
                    map.put(equations[i][0], tmp1);
                }
                if(map.containsKey(equations[i][1])){
                    map.get(equations[i][1]).put(equations[i][0],1 / values[i]);
                }else{
                    Map<String,Double> tmp2 = new HashMap<String,Double>();
                    tmp2.put(equations[i][0],1 / values[i]);
                    map.put(equations[i][1], tmp2);
                }
            }
            double[] res = new double[queries.length];
            for(int i = 0; i < queries.length; i++){
                // query[i][0] / query[i][1]
                if(!map.containsKey(queries[i][0]) || !map.containsKey(queries[i][1])){
                    res[i] = -1.0;
                    continue;
                }
                
                Set<String> visited = new HashSet<String>();
                Double tmp = dfs(queries[i][0], queries[i][1], map, 1.0, visited);
                
                if(tmp == null){
                    res[i] = -1.0;
                }else{
                    res[i] = tmp;
                }
                
            }
            return res;
        }
        
        public Double dfs(String from, String to, Map<String,Map<String,Double>> map, Double curRes, Set<String> visited){
            // base case 1: reach the end
            if(from.equals(to)){
                return new Double(curRes);
            }
            // base case 2 : reach the dead end, no new neighbor is available
            for(Map.Entry<String,Double> entry : map.get(from).entrySet()){
                String neighbor = entry.getKey();
                
                if(visited.contains(neighbor)){
                    continue;
                }
                visited.add(neighbor);
                Double tmp = dfs(neighbor, to, map, curRes * entry.getValue(), visited);
                visited.remove(neighbor);
                
                if(tmp != null){
                    return tmp;
                }
            }
            
            return null;
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.