Alien Dictionary

/**

There is a new alien language which uses the latin alphabet.
However, the order among letters are unknown to you.
You receive a list of words from the dictionary, where words are sorted lexicographically
by the rules of this new language. Derive the order of letters in this language.
For example, Given the following words in dictionary,
[
  "wrt",
  "wrf",
  "er",
  "ett",
  "rftt"
]
The correct order is: "wertf".
Note: You may assume all letters are in lowercase.
If the order is invalid, return an empty string.
There may be multiple valid order of letters, return any one of them is fine.
*/

import java.util.*;
public class AlienDictionary{

/**
Solution:
-the idea is to use topological sorting
-we create a degree map that initializes the degree of each character in the word as zero
-in a loop, take two consecutive words at a time and do the following
-- for the characters upto the length(min(length_word1, length_word2)),
if the character of word1 is not same as the character of the word2,
then the char of word1 should come before the char of word2
-- use a map to put the char of word1 as key and the char of word2 as value in the hashset
-- the degree of char of word2 is also increased by 1
-in second pass, for each character in the degree map, if a character has zero in-degree
then add it to a queue and repeat the following until queue is not empty
--fetch a character from the queue (this character has no incoming edges),
for all the characters in its hashset, decrease the count by 1.
If after decreasing the degree a character's indegree reaches 0, then add it to queue.
Append the fetched character into a result string
-if the length of result string is equal to the size of the degree map, then we are done,
we have all the characters in the given dictionary into our result string.
Return the string as the result
-else return empty string because some of the chars still have non-zero in-degrees
(these can be due to a cycle)
O(nm), where n is the number of words and m is the common length of the consecutive words,
Space is O(m) to store the chars in queue, O(m) to have the character maps and degree maps
*/
public static String alienOrder(String[] words) {
        if(words == null || words.length == 0)
            return "";
        Map<Character, Set<Character>> map = new HashMap<Character, Set<Character>>();
        Map<Character, Integer> degree = new HashMap<Character, Integer>();
        StringBuilder sb = new StringBuilder();
        // put all word in-degree 0
        for(String s: words){
            for(char c: s.toCharArray()){
                degree.put(c,0);
            }
        }
        // compare each word and its pre-word char by char,
        // if different, since c1 is in front of c2, put c2 into c1's next set, c2 in-dgree + 1
        for(int i=0; i < words.length-1; i++){
            String cur = words[i];
            String next = words[i+1];
            // using longer one
            int length = Math.min(cur.length(), next.length());
            for(int j=0; j<length; j++){
                char c1=cur.charAt(j);
                char c2=next.charAt(j);
                if(c1!=c2){
                    Set<Character> set = map.getOrDefault(c1, new HashSet());
                    if(!set.contains(c2)){
                        set.add(c2);
                        map.put(c1, set);
                        degree.put(c2, degree.get(c2) + 1);
                    }
                    break;//the ordering of the rest of the characters in these two words cannot be predicted using this comparision so we break the comparision for the rest of characters in this pair
                }
            }
        }
        // topological sort via BFS
        Queue<Character> q = new LinkedList();
        // put all 0 in-degree into queue
        for(char c: degree.keySet()){
            if(degree.get(c) == 0) q.add(c);
        }
        while(!q.isEmpty()){
            char c = q.poll();
            sb.append(c);
            if(map.containsKey(c)){
                for(char c2: map.get(c)){
                    // all next chars' in-degree abstract 1
                    degree.put(c2,degree.get(c2) - 1);
                    if(degree.get(c2) == 0) q.add(c2);
                }
            }
        }
        if(sb.length() != degree.size()) return "";
        return sb.toString();
    }
public static void main(String[] args){
String[] words = {"wrt", "wrf",  "er",  "ett",  "rftt"};
System.out.println(alienOrder(words));
}
}