269. Alien Dictionary

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

For example,

Given the following words in dictionary,

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

The correct order is: "wertf".

Note:

1. You may assume all letters are in lowercase.
2. If the order is invalid, return an empty string.
3. There may be multiple valid order of letters, return any one of them is fine.

这道题的意思是list of words里面个单词是按字母顺序排列的，而不是每个单词内部是按顺序排列的，这一点需要首先弄清楚。

这里的解题思路是通过list of words找出每个字母之间的顺序关系，建一个graph，如a < b，则a -> b。 然后就可以通过topological sort的方法来确定是否有valid order。

public class Solution {
    public String alienOrder(String[] words) {   // Topological sorting - Kahn's Algorithm
        if(words == null || words.length == 0) {
            return "";
        }
        
        Map<Character, HashSet<Character>> map = new HashMap<>();
        Map<Character, Integer> inDegree = new HashMap<>();
        
        for(String s : words) {
            for(int i = 0; i < s.length(); i++) {
                char c = s.charAt(i);
                inDegree.put(c, 0);
            }
        }
        
        for(int i = 1; i < words.length; i++) {             // find  (prevChar, curChar) pairs as edges
            String prevStr = words[i - 1];
            String curStr = words[i];
            int len = Math.min(prevStr.length(), curStr.length());
            for(int j = 0; j < len; j++) {
                char curChar = curStr.charAt(j);
                char prevChar = prevStr.charAt(j);
                if(curChar == prevChar) {
                    continue;
                } else {                                            // find edges;
                    if(map.containsKey(prevChar)) {
                        if(!map.get(prevChar).contains(curChar)) {
                            map.get(prevChar).add(curChar);
                            inDegree.put(curChar, inDegree.get(curChar) + 1);
                        }
                    } else {
                        HashSet<Character> tmpSet = new HashSet<>();
                        tmpSet.add(curChar);
                        map.put(prevChar, tmpSet);
                        inDegree.put(curChar, inDegree.get(curChar) + 1);
                    }
                    break;
                }
            }
        }
        
        Queue<Character> queue = new LinkedList<>();
        for(char c : inDegree.keySet()) {
            if(inDegree.get(c) == 0) {
                queue.offer(c);
            }
        }
        
        StringBuilder res = new StringBuilder();
        while(!queue.isEmpty()) {
            char c = queue.poll();
            res.append(c);
            if(map.containsKey(c)) {
                for(char l : map.get(c)) {
                    inDegree.put(l, inDegree.get(l) - 1);
                    if(inDegree.get(l) == 0) {
                        queue.offer(l);
                    }
                }
            }
        }
        
        if(res.length() != inDegree.size()) {
            return "";
        }
        
        return res.toString();
    }
}