AlienLanguage

AlienLanguage.java

import java.util.*;

public class AlienLanguage {
  class Graph{
    private Map<Character, LinkedHashSet<Character>> adj;
    public Graph(){
      adj = new HashMap<Character, LinkedHashSet<Character>>();
    }
    public void addEdge(Character st, Character dest){
      LinkedHashSet<Character> chars = new LinkedHashSet<>();
      if(adj.containsKey(st)) chars = adj.get(st);
      chars.add(dest);
      adj.put(st, chars);
    }
    public String topologicalSort(){
      Set<Character> visited = new HashSet<Character>();
      Set<Character> loop = new HashSet<Character>();
      ArrayDeque<Character> queue = new ArrayDeque<Character>();
      for(Map.Entry<Character, LinkedHashSet<Character>> kv: adj.entrySet()){
        if(!visited.contains(kv.getKey())){
          boolean result = topologicalSortUtil(kv.getKey(), adj, visited, queue, loop);
          if(!result) return "";
        }

      }
      StringBuilder builder = new StringBuilder();
      while(!queue.isEmpty()) builder.append(queue.poll());
      return builder.toString();
    }

    private boolean topologicalSortUtil(Character key, Map<Character, LinkedHashSet<Character>> adj, Set<Character> visited,
      ArrayDeque<Character> queue, Set<Character> loop){
      if(visited.contains(key)) return true;
      if(loop.contains(key)) return false;
      loop.add(key);
      if(adj.containsKey(key)){
        LinkedHashSet<Character> set = adj.get(key);
        Iterator<Character> iter = set.iterator();
        while(iter.hasNext())
        {
          boolean ret = topologicalSortUtil(iter.next(), adj, visited, queue, loop);
          if(!ret) return false;
        }
      }
      visited.add(key);
      queue.offerFirst(key);
      return true;
    }
  }

  public String sortDictionary(String[] words){
    Graph g = new Graph();
    for(int i = 0; i < words.length-1; i++){
      String word1 = words[i];
      String word2 = words[i+1];
      for(int j = 0; j < Math.min(word1.length(), word2.length()); j++){
        if(word1.charAt(j) != word2.charAt(j)){
          g.addEdge(word1.charAt(j), word2.charAt(j));
          break;
        }
      }
    }
    return g.topologicalSort();
  }
}