AC Java codes using graph idea


  • 2
    T
    public class Solution {
    
        private class Node{
            String val;
            Map<Node, Double> linkedNodes;
            public Node(String val){
                this.val = val;
                linkedNodes = new HashMap<Node, Double> ();
            }
            
            public void addNode(Node n, double w){
                linkedNodes.put(n, w);
            }
        }
        
        Map<String, Node> nodes;
        public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
            nodes = new HashMap<String, Node>();
            //Construct the graph
            for (int i = 0; i < equations.length; i++){
                Node A; Node B;
                if (nodes.containsKey(equations[i][0])) A = nodes.get(equations[i][0]);
                else { A = new Node(equations[i][0]); nodes.put(equations[i][0], A);}
                if (nodes.containsKey(equations[i][1])) B = nodes.get(equations[i][1]);
                else {B = new Node(equations[i][1]); nodes.put(equations[i][1], B);}
                A.linkedNodes.put(B, values[i]);
                B.linkedNodes.put(A, 1/values[i]);
            }
            //Search in the graph
            double[] res = new double[queries.length];
            for (int i = 0; i < queries.length; i++){
                if (!nodes.containsKey(queries[i][0]) || !nodes.containsKey(queries[i][1])) res[i] = -1;
                else if (  queries[i][0].equals(queries[i][1]) ) res[i] = 1;
                else{
                    Set<String> unVisited = new HashSet(nodes.keySet());
                    res[i] = bfs(nodes.get(queries[i][0]), queries[i][1], unVisited);
                }
            }
            return res;
        }
        
        //May be actrually dfs
        private double bfs(Node n, String target, Set<String> unVisited){
            if (!unVisited.contains(n.val)) return -1;
            else {
                unVisited.remove(n.val);
                
                for (Node subN: n.linkedNodes.keySet()){
                    if (subN.val.equals(target)) return n.linkedNodes.get(subN);
                    double res = bfs(subN, target, unVisited);
                    if (res != -1) return res*n.linkedNodes.get(subN);
                }
                return -1;
            }
        }
    }
    
    

  • 0
    S

    nice and clean code!


  • 0
    D

    Nice solution!


Log in to reply
 

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