Share my Java DFS solution


  • 0
    E

    Basic idea is pretty simple: construct graph and do DFS for each query. The optimization is as long as we find a answer, we can directly jump out from recursion instead of go through all rest of relations since there is no contradiction.

    public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
            double[] result = new double[queries.length];
            
            HashMap<String, HashMap<String, Double>> mapping = new HashMap<String, HashMap<String, Double>>();
            
            // Construct graph
            for (int i = 0; i < equations.length; i++){
                String key = equations[i][0];
                String val = equations[i][1];
                double ratio = values[i];
                if (!mapping.containsKey(key)){
                    HashMap<String, Double> hm1 = new HashMap<String, Double>();
                    mapping.put(key, hm1);
                }
                if (!mapping.containsKey(val)){
                    HashMap<String, Double> hm2 = new HashMap<String, Double>();
                    mapping.put(val, hm2);
                }
                mapping.get(key).put(val, ratio);
                mapping.get(val).put(key, 1.0/ratio);
            }
            int idx = 0;
            
            for (int i = 0; i < queries. length; i++){
                String start = queries[i][0];
                String end = queries[i][1];
                if (mapping.containsKey(start) && mapping.containsKey(end)){
                    boolean[] flag = new boolean[1]; // As long as we find one solution, 
                                                    //we can end the recursion of current query
                    dfs(start, end, "", mapping, result, idx, 1, flag);
                    if(flag[0]){
                        idx++;
                    }else{
                        result[idx++] = -1.0;
                    }
                }else{
                    result[idx++] = -1.0;
                }
            }
            
            return result;
        }
        
    public void dfs(String start, String end, String pre, HashMap<String, HashMap<String, Double>> mapping, double[] result, int idx, double total, boolean[] flag){
            HashMap<String, Double> hm = mapping.get(start);
            if (hm.size() == 0 && !start.equals(end)){
                return;
            }
            
            if (start.equals(end)){
                result[idx] = total;
                flag[0] = true;
                return;
            }
            Iterator it = hm.entrySet().iterator();
            while (it.hasNext()){
                Map.Entry pair = (Map.Entry) it.next();
                String nextString = (String)pair.getKey();
                
                // ignore previous node
                if (!nextString.equals(pre)){
                    Double value = (Double)pair.getValue();
                    dfs(nextString, end, start, mapping, result, idx, total * value, flag);
                    if (flag[0]){
                        return;
                    }
                }
            }
        }
    

Log in to reply
 

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