AC Java using 1 map


  • 0
    H

    My idea was to use one map instead of 2. For each value pair, for example a/b = 3.0, toss <b, 3.0> into a's map and also <a, 1.0/3.0> into b's map. Then use standard dfs to search for the query. For backtracking (i.e., avoiding the condition of searching back to itself), before every dfs delete the entry and put it back after the search on current entry is done. The value of query is just product along the path, which can be done through dfs process.

    public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
        double[] result = new double[queries.length];
        if(equations == null || equations.length == 0 
        || equations[0].length != 2 || equations.length != values.length) return result;
        HashMap<String, Map<String, Double>> map = new HashMap<String, Map<String, Double>>();
        int valueIndex = 0;
        for(String[] equation : equations){
            String exp1 = equation[0];
            String exp2 = equation[1];
            if(!map.containsKey(exp1)){
                HashMap<String, Double> subMap = new HashMap<String, Double>();
                map.put(exp1, subMap);
            }
            if(!map.containsKey(exp2)){
                HashMap<String, Double> subMap = new HashMap<String, Double>();
                map.put(exp2, subMap);
            }
            Map<String, Double> subMap = map.get(exp1);
            subMap.put(exp2, values[valueIndex]);
            map.put(exp1, subMap);
            subMap = map.get(exp2);
            subMap.put(exp1, 1.0 / values[valueIndex]);
            map.put(exp2, subMap);
            valueIndex++;
        }
        for(int i = 0; i < queries.length; i++){
            String q1 = queries[i][0];
            String q2 = queries[i][1];
            result[i] = dfs(map, q1, q2);
        }
        return result;
    }
    
    private double dfs(HashMap<String, Map<String, Double>> map, String start, String end){
        if(!map.containsKey(start)) return -1.0;
        if(map.get(start).containsKey(end)) return map.get(start).get(end);
        
        Map<String, Double> subMap = map.remove(start);
        double currentVal = -1.0;
        for(String str : subMap.keySet()){
            double result = dfs(map, str, end);
            if(result != -1.0){
                currentVal = subMap.get(str) * result;
                break;
            }
        }
        map.put(start, subMap);
        return currentVal;
    }

Log in to reply
 

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