Java Solution basic Topological Sort


  • 1
    C
    public class Solution{
    	private class Node{
    		private char id;
    		private Set<Node> in;
    		private Set<Node> out;
    		public Node(Character id){
    			this.id = id;
    			this.in = new HashSet<>();
    			this.out = new HashSet<>();
    		}
    	}
    	public String alienOrder(String[] words){
    		Map<Character, Node> graph = new HashMap<Character, Node>(); 
    		for(int i = 0; i < words.length; i++){
    			for(int j = 0; j < words[i].length(); j++){
    				if(!graph.containsKey(words[i].charAt(j))){
    					graph.put(words[i].charAt(j), new Node(words[i].charAt(j)));
    				}
    			}
    			if(i > 0){
    				getOrder(words[i - 1], words[i], graph);
    			}
    		}
    		return topSort(graph);
    	}
    
    	private void getOrder(String s, String t, Map<Character, Node> graph){
    		for(int i = 0; i < Math.min(s.length(), t.length()); i++){
    			Node n1 = graph.get(s.charAt(i)), n2 = graph.get(t.charAt(i));
    			if(!n1.equals(n2)){
    				n1.out.add(n2);
    				n2.in.add(n1);
    				break;
    			}
    		}
    	}
    
    	private String topSort(Map<Character, Node> graph){
    		StringBuilder sb = new StringBuilder();
    		Queue<Node> queue = new LinkedList<>();
    		for(char c : graph.keySet()){
    			if(graph.get(c).in.size() == 0){
    				queue.offer(graph.get(c));
    			}
    		}
    		while(!queue.isEmpty()){
    			Node tmp = queue.poll();
    			sb.append(tmp.id);
    			for(Node n : tmp.out){
    				n.in.remove(tmp);
    				if(n.in.size() == 0){
    					queue.offer(n);
    				}
    			}
    		}
    		if(sb.length() != graph.size()) return "";
    		return sb.toString();
    	}
    }

Log in to reply
 

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