Java 5ms BFS Solution, 75 lines of code


  • 0

    Basic idea:
    1.Construct graph. The value can be treated as weight (or cost).
    2.Find the path, get the result.

    public class Solution {
        public void addNewNode(HashMap<String, Node> graph, double value, String first, String second, boolean isFirst){
        	if(graph.containsKey(first)){
        			Node tmp = graph.get(first);
        			tmp.adj.add(second);
        			if(isFirst)tmp.weight.add(value);
        			else tmp.weight.add(1.0/value);
        	}else{
        			List<String> adj = new ArrayList<String>();
        			adj.add(second);
        			List<Double> weight = new ArrayList<Double>();
        			if(isFirst)weight.add(value);
        			else weight.add(1.0/value);
        			graph.put(first, new Node(first, adj, weight));
        	}
        }	
    
        public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
            HashMap<String, Node> graph = new HashMap<String,Node>();
    		int n = values.length;
    		int resLen = queries.length;
    		double[] res = new double[resLen];
    		if(n == 0) return res;
    		for(int i = 0; i < n; i++){
    			String first = equations[i][0], second = equations[i][1];
    			addNewNode(graph, values[i], first, second, true);
    			addNewNode(graph, values[i], second, first, false);
    		}	
    
    		for(int i = 0; i < resLen; i++){
    			String first = queries[i][0], second = queries[i][1];
    			if(!graph.containsKey(first) || !graph.containsKey(second)){
    				res[i] = -1.0;
    				continue;
    			 }
    			res[i] = bfs(graph, first, second);
            }
            return res;
        }
        public double bfs(HashMap<String, Node> graph, String start, String end){
        	Queue<String> queue = new LinkedList<String>();
        	queue.add(start);
        	Queue<Double> resQ = new LinkedList<Double>();
        	resQ.add(new Double(1.0));
        	HashMap<String,Integer> vis = new HashMap<String, Integer>();
        	vis.put(start,0);
        	while(!queue.isEmpty()){
        	  String cur = queue.poll();		
        		Node tmp = graph.get(cur);
        		double val = resQ.poll();
        		if(cur.equals(end)){
        			return val;
        		}
        		for(int i = 0; i < tmp.adj.size(); i++){
        		    String adjNode = tmp.adj.get(i);
        		    if(!vis.containsKey(adjNode)){
        		        vis.put(adjNode, 0);
        		        queue.add(tmp.adj.get(i));
        			    resQ.add(val*tmp.weight.get(i));
        		    }
        		}
        	}
    	    return -1.0;
        }
    }
    class Node{
    	String name;
    	List<String> adj;
    	List<Double> weight;
    	public Node(String name, List<String> adj, List<Double> weight){
    		this.name = name;
    		this.adj = adj;
    		this.weight = weight;
    	}
    }	
    

Log in to reply
 

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