JAVA very easy solution using DFS


  • 1
    C
    public class Solution
    {
        private Double result;
        private HashMap<String, Set<String>> map = new HashMap<String, Set<String>>();
        private HashMap<String, Double> valueMap = new HashMap<String, Double>();
        
        public double[] calcEquation(String[][] equations, double[] values, String[][] queries)
        {
            
            double[] res = new double[queries.length];
            
            for(int i = 0; i < equations.length; i++)
            {
                if(null == map.get(equations[i][0]))
                {
                    map.put(equations[i][0], new HashSet<String>());
                }
                if(null == map.get(equations[i][1]))
                {
                    map.put(equations[i][1], new HashSet<String>());
                }
                
                map.get(equations[i][0]).add(equations[i][1]);
                map.get(equations[i][1]).add(equations[i][0]);
                
                valueMap.put(equations[i][0] + "/" + equations[i][1], values[i]);
                valueMap.put(equations[i][1] + "/" + equations[i][0], (double) 1 / values[i]);
            }
            
            for(int i = 0; i < queries.length; i++)
            {
                HashSet<String> visited = new HashSet<String>();
                
                String src = queries[i][0];
                String dest = queries[i][1];
                
                if(src.equals(dest) && map.containsKey(src))
                {
                    res[i] = 1.0;
                }
                else
                {
                    if(!map.containsKey(src) || !map.containsKey(dest))
                    {
                        res[i] = -1.0;
                    }
                    else
                    {
                        result = Double.MAX_VALUE;
                        
                        dfs(src, dest, visited, 1.0);
                        
                        res[i] = result == Double.MAX_VALUE ? -1.0 : result; 
                    }
                }
            }
            
            return res;
        }
        
        private void dfs(String src, String dest, HashSet<String> visited, Double val)
        {
            visited.add(src);
            
            if(src.equals(dest))
            {
                result = val;
                return;
            }
            
            for(String neighbor : map.get(src))
            {
                if(!visited.contains(neighbor))
                {
                    dfs(neighbor, dest, visited, val * valueMap.get(src + "/" + neighbor));
                }
            }
        }
        
        
    }

Log in to reply
 

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