Java HashMap DFS solution, 3ms


  • 0
    F
    public class Solution {
        public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
            HashMap<String, Double> nums = new HashMap();
            HashMap<String, List<Integer>> edges = new HashMap();
            HashMap<String, Integer> group = new HashMap();
            
            // build the graph, count the in-degree of each node
            for (int i = 0; i < values.length; i++) {
                String[] curPair = equations[i];
                // make undirected graph directed
                if (nums.containsKey(curPair[1]) && nums.get(curPair[1]) < 0.0) {
                    String temp = curPair[0];
                    curPair[0] = curPair[1];
                    curPair[1] = temp;
                    values[i] = 1 / values[i];
                }
                String start = curPair[0], end = curPair[1];
                if (!nums.containsKey(start)) {
                    nums.put(start, 0.0);
                }
                nums.put(end, nums.getOrDefault(end, 0.0) - 1.0);
                List<Integer> edge = edges.get(start);
                if (edge == null) {
                    edge = new ArrayList();
                    edges.put(start, edge);
                }
                edge.add(i);
            }
            
            // iterate the graph via DFS, group the nodes and calculate the value of each node
            int groupId = 0;
            for (Map.Entry<String, Double> numEntry : nums.entrySet()) {
                if (numEntry.getValue() == 0.0) {
                    numEntry.setValue(1.0);
                    String start = numEntry.getKey();
                    dfs(nums, edges, group, start, groupId++, equations, values);
                }
            }
            
            // make queries O(N)
            double[] result = new double[queries.length];
            for (int i = 0; i < queries.length; i++) {
                String s = queries[i][0], e = queries[i][1];
                result[i] = -1.0;
                if (group.get(s) != null && group.get(s) == group.get(e)) {
                    result[i] = nums.get(s) / nums.get(e);
                }
            }
            return result;
        }
        
        private void dfs(HashMap<String, Double> nums, HashMap<String, List<Integer>> edges , HashMap<String, Integer> group, String start, int groupId, String[][] equations, double[] values) {
                
            group.put(start, groupId);
            List<Integer> nextEdges = edges.get(start);
            if (nextEdges != null) {
                for (int edgeIdx : nextEdges) {
                    String s = equations[edgeIdx][0], e = equations[edgeIdx][1];
                    nums.put(e, nums.get(s) / values[edgeIdx]);
                    dfs(nums, edges, group, e, groupId, equations, values);
                }
            }
        }
    }
    

Log in to reply
 

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