Java DFS solution


  • 0
    K
    public class Solution {
        public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
            HashMap<String, List<Vertex>> graph = new HashMap<>();
            double[] res = new double[queries.length];
            for(int i = 0; i < values.length; ++i)
            {
                addNode(graph, equations[i][0], equations[i][1], values[i]);
                addNode(graph, equations[i][1], equations[i][0], 1/values[i]);
            }
            
            for(int i = 0; i < queries.length; ++i)
            {
                if(!graph.containsKey(queries[i][0]) || !graph.containsKey(queries[i][1]))
                {
                    res[i] = -1;
                    continue;
                }
                res[i] = getSolution(graph, queries[i][0], queries[i][1], 1, new HashSet<String>());
            }
            return res;
            
        }
        
        private double getSolution(HashMap<String, List<Vertex>> graph, String s, String d, double mul, HashSet<String> hs)
        {
            if(d.equals(s)) return mul;
            hs.add(s);
            double tmp = -1;
            for(Vertex v:graph.get(s))
            {
                if(hs.contains(v.name)) continue;
                tmp = getSolution(graph, v.name, d, mul*v.mul, hs);
                if(tmp != -1) break;
            }
            hs.remove(s);
            return tmp;
        }
        
        private void addNode(HashMap<String, List<Vertex>> graph, String s, String d, double val)
        {
            if(graph.containsKey(s))
            {
                graph.get(s).add(new Vertex(val, d));
            }
            else
            {
                List<Vertex> l = new ArrayList<Vertex>();
                l.add(new Vertex(val, d));
                graph.put(s, l);
            }
        }
        
        private class Vertex
        {
            double mul;
            String name;
            public Vertex(double mul, String name)
            {
                this.name = name;
                this.mul = mul;
            }
        }
    }
    

Log in to reply
 

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