2 general Solutions based on BFS topological sort


  • 0
    //Solution 1: build successor set for every character
    public String alienOrder(String[] words) {
        Map<Character, Set<Character>> successorMap=new HashMap<Character, Set<Character>>();
        Set<Character> CharacterSet=new HashSet<Character>();
        for(int i=0; i<words.length; i++){
        	for(int j=0; j<words[i].length(); j++)
        		CharacterSet.add(words[i].charAt(j)); //add all chars to CharacterSet
        }
        //Build char->successorSet
        for(int i=0; i<words.length-1; i++){
            String cur=words[i],next = words[i+1];
            int length=Math.min(cur.length(), next.length());
            for(int j=0; j<length; j++){
            	char c1=cur.charAt(j),c2 = next.charAt(j);
                if(c1!=c2){
                    Set<Character> successor=new HashSet<Character>();
                    if(successorMap.containsKey(c1)) successor=successorMap.get(c1);
                    if(!successor.contains(c2)){
                        successor.add(c2);
                        successorMap.put(c1, successor);
                    }
                    break;
                }
            }
        }
        Queue<Character> bfs =new LinkedList<Character>();
        for(char c: CharacterSet) 
        	if(!successorMap.containsKey(c)) bfs.add(c);
        StringBuilder result = new StringBuilder();
        while(!bfs.isEmpty()){
            char c=bfs.remove(); result.append(c);
                	for(char charkey: successorMap.keySet()){
                		Set<Character> successor = successorMap.get(charkey);
                		if(successor.contains(c)){
                			successor.remove(c);
                			if(successor.isEmpty()) bfs.add(charkey);
                		}
                	}
        }
        if(result.length()!=CharacterSet.size()) return "";
        return result.reverse().toString();
    }
    
    
    //Solution 2: build predecessor set for every character
    public String alienOrder2(String[] words) {
        Map<Character, Set<Character>> predecessorMap=new HashMap<Character, Set<Character>>();
        Set<Character> CharacterSet=new HashSet<Character>();
        for(String s: words)
        	for(char c: s.toCharArray()) 
        	    CharacterSet.add(c);
      //Build char->predecessorSet
        for(int i=0; i<words.length-1; i++){
            String cur=words[i],next=words[i+1];
            int length=Math.min(cur.length(), next.length());
            for(int j=0; j<length; j++){
                char c1=cur.charAt(j),c2 = next.charAt(j);
                if(c1!=c2){
                    Set<Character> predecessor=new HashSet<Character>();
                    if(predecessorMap.containsKey(c2)) predecessor=predecessorMap.get(c2);
                    if(!predecessor.contains(c1)){
                    	predecessor.add(c1);
                        predecessorMap.put(c2, predecessor);
                    }
                    break;
                }
            }
        }
        Queue<Character> bfs =new LinkedList<Character>();
        //put into Queue all Characters without predecessor
        for(char c: CharacterSet)
        	if(!predecessorMap.containsKey(c)) bfs.add(c);
        StringBuilder result = new StringBuilder();
        //BFS toplocial sort
        while(!bfs.isEmpty()){
            char c=bfs.poll();
            result.append(c);
        	for(char charkey: predecessorMap.keySet()){
        		Set<Character> predecessor = predecessorMap.get(charkey);
        		if(predecessor.contains(c)){
        			predecessor.remove(c);
        			if(predecessor.isEmpty()) bfs.add(charkey);
        		}
        	}
        }
        if(result.length()!=CharacterSet.size()) return "";//return if there's cycle
        return result.toString();
    }

Log in to reply
 

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