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.
Note:
You may assume all letters are in lowercase.
You may assume that if a is a prefix of b, then a must appear before b in the given dictionary.
If the order is invalid, return an empty string.
There may be multiple valid order of letters, return any one of them is fine.

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 "".

拓扑排序：http://www.jianshu.com/p/5880cf3be264

Solution：拓扑排序

思路： 建图(map(node -> set)) ＋ 拓扑排序

words num = n
words len = m
Time Complexity: O(mn) Space Complexity: O(mn)

Solution Code：

class Solution {
    public String alienOrder(String[] words) {
        StringBuilder result = new StringBuilder();
        if(words == null || words.length==0) return result.toString();
        
        Map<Character, Set<Character>> graph = new HashMap<>();
        Map<Character, Integer> indegree = new HashMap<>();
        
        // graph init and indegree init
        for(String s: words){
            for(char c: s.toCharArray()){
                indegree.put(c,0);
            }
        }
        
        for(int i = 0; i < words.length - 1; i++){
            String cur = words[i];
            String next = words[i+1];
            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){
                    if(!graph.containsKey(c1)) {
                        graph.put(c1, new HashSet<>());
                    }
                    Set<Character> next_set = graph.get(c1);
                    if(!next_set.contains(c2)){
                        next_set.add(c2);
                        indegree.put(c2, indegree.get(c2) + 1);
                    }
                    break;
                }
            }
        }
        
        // bfs
        Queue<Character> queue = new LinkedList<>();
        for(char c: indegree.keySet()){
            if(indegree.get(c) == 0) {
                queue.add(c);
            }
        }
        
        while(!queue.isEmpty()){
            char c = queue.poll();
            result.append(c);
            if(graph.containsKey(c)) {
                for(char next: graph.get(c)){
                    indegree.put(next, indegree.get(next) - 1);
                    if(indegree.get(next) == 0) {
                        queue.add(next);
                    }
                }
            }
        }
        if(result.length() != indegree.size()) return "";
        return result.toString();
    }
}