Alien Dictionary

Solution.java

class Solution {
  
  
  public String alienOrder(String[] words) {
    if (words == null || words.length == 0) {
      return "";
    }
    Map<Character, Set<Character>> graph = new HashMap<>(); // List -> Set?
    Map<Character, Integer> indegree = new HashMap<>();
    
    buildGraph(words, graph, indegree);
    
    // bfs
    Queue<Character> queue = new LinkedList<>();
    // push all 0-indegree nodes
    for (char v : graph.keySet()) {
      if (indegree.get(v) == 0) {
        queue.offer(v);
      }
    }
    
    int count = graph.size(); // number of nodes in total
    StringBuilder sb = new StringBuilder();
    while (queue.size() > 0) {
      char v = queue.poll();
      sb.append(v);
      --count;
      Set<Character> neighborList = graph.get(v);
      // for each neighbor w
      for (char w : neighborList) {
        int degree = indegree.get(w);
        indegree.put(w, degree - 1);
        if (degree - 1 == 0) {
          queue.offer(w);
        }
      }
    }
    
    if (count == 0) return sb.toString();
    else            return "";
  }
  
  
  private void buildGraph(String[] words, Map<Character, Set<Character>> graph, Map<Character, Integer> indegree) {
    // preprocess
    for (int i = 0; i < words.length; ++i) {
      for (int j = 0; j < words[i].length(); ++j) {
        char ch = words[i].charAt(j);
        graph.put(ch, graph.getOrDefault(ch, new HashSet<>()));
        indegree.put(ch, 0);
      }
    }
    
    // add edges and calculate indegrees
    for (int i = 0; i < words.length - 1; ++i) {
      String s1 = words[i];
      String s2 = words[i + 1];
      int j = 0;
      while (j < s1.length() && j < s2.length() && s1.charAt(j) == s2.charAt(j)) {
        ++j;
      }
      // consider: "abc" vs. "abcd", "abc" vs. "abc", "abcd" vs. "abc" -> no info. gained
      if (j < s1.length() && j < s2.length()) {
        char c1 = s1.charAt(j);
        char c2 = s2.charAt(j);
        if (graph.get(c1).contains(c2) == false) { // critical
          graph.get(c1).add(c2);
          indegree.put(c2, indegree.getOrDefault(c2, 0) + 1); // indegree
        }
      }
    }
  }
  
  
}