269. Alien Dictionary

Problem:

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 non-empty words from the dictionary, where words are sorted lexicographically by the rules of this new language. Derive the order of letters in this language.

Example 1:
Given the following words in dictionary,

[
  "wrt",
  "wrf",
  "er",
  "ett",
  "rftt"
]

The correct order is: "wertf".

Example 2:
Given the following words in dictionary,

[
  "z",
  "x"
]

The correct order is: "zx".

Example 3:
Given the following words in dictionary,

[
  "z",
  "x",
  "z"
]

The order is invalid, so return "".

Note:

1. You may assume all letters are in lowercase.
2. You may assume that if a is a prefix of b, then a must appear before b in the given dictionary.
3. If the order is invalid, return an empty string.
4. There may be multiple valid order of letters, return any one of them is fine.

Analysis:
6/8/2018 update:
Why initialize graph and degrees first?
1. There will be no char with degree 0 if we don't initialize degrees
2. In BFS, the last char is not in graph, will cause null pointer error. 
--------------------------------------------------------------------------------------------------------------------------------------------

Lexicographical order is just compare the first char that is not equal. Edges are built from the differences. Each two adjacent  word can only have one diff in lexicographical order. 

Solution:

class Solution {
    public String alienOrder(String[] words) {
        Map<Character, Integer> degree = new HashMap<>();
        Map<Character, Set<Character>> graph = new HashMap<>();
        
        // intialize degree
        for (String s: words) {
            for (char c: s.toCharArray()) {
                degree.put(c, 0);
                graph.put(c, new HashSet<>());
            }
        }
        // intialize graph
        for (int i = 0; i < words.length - 1; i++) {
            char[] word1 = words[i].toCharArray();
            char[] word2 = words[i + 1].toCharArray();
            int len = Math.min(word1.length, word2.length);
            for (int j = 0; j < len; j++) {
                if (word1[j] != word2[j]) {
                    // word1[j] -> word2[j]
                    if(graph.get(word1[j]).add(word2[j])) {
                      degree.put(word2[j], degree.get(word2[j]) + 1);     
                    }
                 break;   
                }
            }
        }
        // get start nodes
        Queue<Character> queue = new LinkedList<>();
        String res = "";
        for (char c: degree.keySet()) {
            if (degree.get(c) == 0) {
                queue.offer(c);
            }
        }
        
        while(!queue.isEmpty()) {
            char cur = queue.poll();
            res += cur;
            for (char neib: graph.get(cur)) {
                degree.put(neib, degree.get(neib) - 1);
                if (degree.get(neib) == 0) {
                    queue.add(neib);
                }
            }
        }
        
        return res.length() == degree.size()? res: "";
    } 
}