Graph Java Solution


  • 1

    For the example:

    equations = [ ["a", "b"], ["b", "c"] ],
    values = [2.0, 3.0],
    queries = [ ["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"] ]. 
    

    build a graph like this:
    0_1473673427632_download.png

    connecting each the terms of each expression with a directed edge of weight 'value', and an inverted edge with weight 1/'value'.

    Then you can compute the result of each query just by searching a path in the graph from var1 to var2, and multiplying the weights. E.g: ["a","c"] = a -> b -> c = 2.0 * 3.0 = 6.0
    Remember to keep track of the visited nodes in the dfs , and stop as soon as you got a valid result. Return -1.0 if you hit a dead end.

    Here is my code:

    public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
    	double[] results = new double[queries.length];
    	Map<String,List<String>> graph = buildGraph(equations,values);
    	for(int i=0;i<queries.length;i++) {
    		String[] query = queries[i];
    		if(query[0].equals(query[1]) && !graph.containsKey(query[0])) {
    			results[i]=-1.0;
    		}
    		else {
    			double result = computeResultDFS(graph,query);
    			results[i] = result;
    		}
    	}
    	return results;
    }
    	
    public double computeResultDFS(Map<String,List<String>> graph, String[] query) {
    	String dividend = query[0];
    	String divisor = query[1];
    	Set<String> visited = new HashSet<>();
    	double result = 1.0;
    	result = dfs(dividend,divisor,graph,visited);
    	if(result<0) result = -1.;
    	return result;
    }
    	
    public double dfs(String start, String end, Map<String,List<String>> graph, Set<String> visited) {
    	if(start.equals(end)) return 1.0;
    	if(visited.contains(start)) return -1.0;
    	visited.add(start);
    	List<String> edgesList = graph.get(start);
    	if(edgesList==null || edgesList.isEmpty()) return -1.0;
    	double result = 1.0;
    	for(String edge: edgesList) {
    		String[] tokens = edge.split(" ");
    		String next = tokens[0];
    		double val = Double.parseDouble(tokens[1]);
    		result = val * dfs(next,end,graph,visited);
    		if(result>0) return result;
    	}
    	return result;
    }
    	
    public Map<String,List<String>> buildGraph(String[][] equations, double[] values) {
    	Map<String,List<String>> graph = new HashMap<>();
    	for(int i=0;i<equations.length;i++) {
    		String startNode = equations[i][0];
    		String endNode = equations[i][1];
    		double value = values[i];
    		String endEdge = endNode+" "+value;
    		String startEdge = startNode+" "+(1/value);
    		if(graph.containsKey(startNode)) {
    			graph.get(startNode).add(endEdge);
    		} else {
    			List<String> edges = new ArrayList<>();
    			edges.add(endEdge);
    			graph.put(startNode, edges);
    		}
    		if(graph.containsKey(endNode)) {
    			graph.get(endNode).add(startEdge);
    		} else {
    			List<String> edges = new ArrayList<>();
    			edges.add(startEdge);
    			graph.put(endNode, edges);
    		}
    	}
    	return graph;
    }
    

Log in to reply
 

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