Java solution using topological sorting


  • 0
    M
    public class Solution {
        
        public String alienOrder(String[] words) {
    	
    		if(words == null || words.length == 0) return "";
    		if(words.length == 1) return words[0];
    		
    		Map<Vertex, Set<Vertex>> dGraph = new HashMap<Vertex, Set<Vertex>>();
    		int minLength = 0;
    		int j = 0;
    		
    		for(int i = 0; i<words.length; i++) {
    			
    			if(i<words.length-1) {
    				minLength = Math.min(words[i].length(),words[i+1].length());
    				for(j =0; j<minLength;j++) {
    					if(words[i].charAt(j) == words[i+1].charAt(j)) {
    						addCharacterInGraph(dGraph,new Vertex(words[i].charAt(j)));
    					} else {
    						createDependency(dGraph,new Vertex(words[i].charAt(j)),new Vertex(words[i+1].charAt(j)));
    						break;
    					}
    				}
    			}
    			
    			for(int t = j;t< words[i].length();t++) {
    				addCharacterInGraph(dGraph,new Vertex(words[i].charAt(t)));
    			}
    		}
    	
    		int resultIndex = dGraph.keySet().size();
    		
    		char[] result = new char[resultIndex];
    		
    		while(dGraph.size()!=0) {
    			
    			Vertex c = dGraph.keySet().iterator().next();
    			Vertex vertexWithNoSuccessor = getVertexWithNoSuccessor(dGraph,c);
    			if(vertexWithNoSuccessor==null) return "";
    			result[--resultIndex] = vertexWithNoSuccessor.c;
    			deleteVertex(dGraph,vertexWithNoSuccessor);
    	
    		}
    	
    		return String.valueOf(result);
        }
    
        private Vertex getVertexWithNoSuccessor(Map<Vertex, Set<Vertex>> dGraph, Vertex cVertex) {
    
    	    if(dGraph.get(cVertex).size()==0) return cVertex;
    	    
    	    cVertex.isVisited = true;
    	    for(Vertex v : dGraph.get(cVertex)) {
    	    	if(!v.isVisited) {
    	    		Vertex r = getVertexWithNoSuccessor(dGraph, v);
    			    if(r!=null) {
    			    	return r;
    			    }
    	    	}
    	    }
    	    
    	    return null;
    
        }
    
        private void deleteVertex(Map<Vertex, Set<Vertex>> dGraph, Vertex c ) {
    
        	dGraph.remove(c);
            for(Vertex v : dGraph.keySet()) {
    	        if(dGraph.get(v).contains(c)) {
    	        	dGraph.get(v).remove(c);
    	        }
    	        for(Vertex cVertex : dGraph.get(v)) {
    	        	cVertex.isVisited = false;
    	        }
            }
    
        }
    
        private void addCharacterInGraph(Map<Vertex, Set<Vertex>> dGraph, Vertex a) {
    	    if(!dGraph.containsKey(a)) {
    	    	dGraph.put(a, new HashSet<Vertex>());
    	    }
        }
    
        private void createDependency(Map<Vertex, Set<Vertex>> dGraph, Vertex a, Vertex b ) {
    	    addCharacterInGraph(dGraph,a);
    	    addCharacterInGraph(dGraph,b);
    	    dGraph.get(a).add(b);
        }
    }
    
    class Vertex {
    
    	Character c ; 
    	boolean isVisited;
    	
    	public Vertex(Character c) {
    		this.c = c;
    		isVisited = false;
    	}
    	
    	public String toString() {
    		return c + " : " + isVisited;
    	}
    	
    	@Override
    	public int hashCode() {
    		return c;
    	}
    	
    	
    	@Override
    	public boolean equals(Object v) {
    		if(this == v) return true;
    		
    		if(v instanceof Vertex) {
    			return this.c == ((Vertex)v).c;
    		}
    		
    		return false;
    	}
    
    }
    

Log in to reply
 

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