AlienDictionary.java

class Solution {
  public String alienOrder(String[] words) {
       //For catching Errors
       if(words.length==0) return "";
       //The dependencyMap and countMap data structures 
       Map<Character, Set<Character>> dependencyMap = new HashMap<>();
       Map<Character, Integer> countMap = new HashMap<>();
       //a boolean that determines whether we can build a graph or not
       boolean success = buildGraph(words, dependencyMap, countMap);
       if(!success) return "";
       //running BFS and returning the result string
       return bfs(dependencyMap, countMap);
   }
  //running BFS on dependency and count map
   String bfs(Map<Character, Set<Character>> dependencyMap,  
                Map<Character, Integer> countMap) {
       Queue<Character> q=new LinkedList<>();
      //Looping over countMap. If the number of dependencies for
     //a letter is 0, add it to the queue.
       for(Map.Entry<Character, Integer> entry:countMap.entrySet()) {
           if(entry.getValue()==0) {
               q.add(entry.getKey());
           }
       }
       //Result string
       StringBuilder result = new StringBuilder();

       //Poping out the letter out of the queue, removing it from
       //countMap and adding it to the string result
       while(!q.isEmpty()) {
           char c=q.poll();
           countMap.remove(c);
           result.append(c);

           if(!dependencyMap.containsKey(c)) continue;
           //Finds the letter's dependent characters and decreases
           //their number of dependencies by one.
           //If the character's dependencies == 0, add it to the queue.
           for(char next:dependencyMap.get(c)) {
               countMap.put(next, countMap.get(next)-1);
               if(countMap.get(next)==0) q.add(next);
           }
       }
       //By the end of the while loop, the countMap must be empty. 
       //Otherwise, there's a loop, and we have no answers
       if(countMap.size()!=0) return "";
       return result.toString();
   }
   //A function that checks whether we can build a graph with given 
   //inputs and fills in dependencyMap and countMap with proper values.
   boolean buildGraph(String[] words, Map<Character, Set<Character>> 
                      dependencyMap, Map<Character, Integer> countMap) {

       //Initiating the countMap
       for(String word:words){
           for(char c:word.toCharArray()) {
                   countMap.putIfAbsent(c, 0);
           }
       } 

       for(int i=1;i < words.length; i++) {
 
           //Comparing every words with its previous word to find 
           //the order of the letters. If they are equal, skip.
           //If the next word starts with the previous word, 
           //there is no answer.
           if(words[i].equals(words[i-1])) continue;
           if(words[i-1].startsWith(words[i])) return false;

           for(int j=0;j < Math.min(words[i].length(),
               words[i-1].length());j++) {
               char firstChar=words[i-1].charAt(j);
               char secondChar=words[i].charAt(j);
               if(firstChar==secondChar) continue;
               //Adding the letter and its dependency to dependencyMap 
               //and countMap.
               dependencyMap.putIfAbsent(firstChar, new HashSet<>());
               if(dependencyMap.get(firstChar).add(secondChar)) {
                   countMap.put(secondChar, countMap.get(secondChar)+1);
               }
               break;
           }
       }
       return true;
   }
}