4ms Java Solution with HashMap and DFS, easy to understand.


  • 0
    public class Solution {
        public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
            Map<String, List<String>> keyMap = new HashMap<String, List<String>>();
            Map<String, List<Double>> valueMap = new HashMap<String, List<Double>>();
            for (int i = 0; i < equations.length; i++) {
                String[] equation = equations[i];
                if (!keyMap.containsKey(equation[0])) {
                    keyMap.put(equation[0], new ArrayList<String>());
                    valueMap.put(equation[0], new ArrayList<Double>());
                }
    
                if (!keyMap.containsKey(equation[1])) {
                    keyMap.put(equation[1], new ArrayList<String>());
                    valueMap.put(equation[1], new ArrayList<Double>());
                }
                keyMap.get(equation[0]).add(equation[1]);
                keyMap.get(equation[1]).add(equation[0]);
                valueMap.get(equation[0]).add(values[i]);
                valueMap.get(equation[1]).add(1 / values[i]);
            }
            double[] res = new double[queries.length];
            for (int i = 0; i < queries.length; i++) {
                res[i] = dfs(keyMap, valueMap, 1.0, new HashSet<String>(), queries[i][0], queries[i][1]);
            }
            return res;
        }
    
    
        public double dfs(Map<String, List<String>> keyMap, Map<String, List<Double>> valueMap, double result, Set<String> visited, String curKey, String targetKey) {
            if (!keyMap.containsKey(curKey) || !keyMap.containsKey(targetKey)) {
                return -1.0;
            }
    
            if (curKey.equals(targetKey)) {
                return result;
            }
    
            List<String> keyList = keyMap.get(curKey);
            List<Double> valueList = valueMap.get(curKey);
            visited.add(curKey);
            double res = - 1.0;
            for (int i = 0; i < keyList.size(); i++) {
                if (!visited.contains(keyList.get(i))) {
                    double val = dfs(keyMap, valueMap, result * valueList.get(i), visited, keyList.get(i), targetKey);
                    if (val != -1.0) {
                        res = val;
                        break;
                    }
                }
            }
            visited.remove(curKey);
            return res;
        }
    }
    

Log in to reply
 

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