Java clean code using graph and dfs


  • 0
    M
    public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
    		HashMap<String,HashMap<String,Double>> graph=makeGraph(equations,values);
    		double[] res=new double[queries.length];
    		HashSet<String> visited=new HashSet<>();
    		for(int i=0;i<queries.length;i++){
    			visited.add(queries[i][0]);
    			res[i]=backstrack(graph,visited,queries[i][0],queries[i][1]);
    			visited.remove(queries[i][0]);
    		}
    		return res;
        }
    	
    	public HashMap<String,HashMap<String,Double>> makeGraph(String[][] equations, double[] values){
    		int n=equations.length;
    		HashMap<String,HashMap<String,Double>> graph=new HashMap<>();
    		for(int i=0;i<n;i++){
    			graph.computeIfAbsent(equations[i][0], k->new HashMap<>()).put(equations[i][1], values[i]);
    			graph.get(equations[i][0]).put(equations[i][0], 1.0);
    			graph.computeIfAbsent(equations[i][1], k->new HashMap<>()).put(equations[i][0], 1.0/values[i]);
    			graph.get(equations[i][1]).put(equations[i][1], 1.0);
    		}
    		return graph;
    	}
    	
    	public double backstrack(HashMap<String,HashMap<String,Double>> graph,HashSet<String> visited,
    			String curr, String dest){
    		if(!graph.containsKey(curr)){
    		    return -1;
    		}
    		if(graph.get(curr).containsKey(dest)){
    			return graph.get(curr).get(dest);
    		}
    		for(String s:graph.get(curr).keySet()){
    			if(visited.contains(s)){
    				continue;
    			}
    			visited.add(s);
    			double r=backstrack(graph,visited,s,dest);
    			visited.remove(s);
    			if(r!=-1){
    				graph.get(curr).put(dest, graph.get(curr).get(s) * r);
    				return graph.get(curr).get(dest);
    			}
    		}
    		return -1;
    	}
    

Log in to reply
 

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