There is a new alien language which uses the latin alphabet. However, the order among letters are unknown to you. You receive a list ofnon-emptywords from the dictionary, wherewords 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.

tag: topological sort

class Solution {
    public String alienOrder(String[] words) {
        if (words == null || words.length == 0) return "";

        Map<Character, Set<Character>> hash = new HashMap<>();
        Map<Character, Integer> inDegree = new HashMap<>();
        Set<String> handled = new HashSet<>();

        Set<Character> set = new HashSet<>();
        for (String word : words){
            for (char c : word.toCharArray()){
                set.add(c);
            }
        }

        for (Character c : set){
            hash.put(c, new HashSet<>());
            inDegree.put(c, 0);
        }


        for (int i = 0; i < words.length - 1; i++){
            for (int j = i + 1; j < words.length; j++){
                String strA = words[i];
                String strB = words[j];
                int index = 0;

                while (index < strA.length() && index < strB.length() && strA.charAt(index) == strB.charAt(index)){
                    index++;
                }

                if (index < strA.length() && index < strB.length()){
                    char charA = strA.charAt(index);
                    char charB = strB.charAt(index);

                    if (handled.contains(charA + "->" + charB)) continue;
                    hash.get(charA).add(charB);
                    inDegree.put(charB, inDegree.get(charB) + 1);
                    handled.add(charA + "->" + charB);
                }
            }
        }

        Queue<Character> q = new LinkedList<>();
        StringBuilder sb = new StringBuilder();
        Set<Character> seen = new HashSet<>();
        for (Character c : inDegree.keySet()){
            if (inDegree.get(c) == 0){
                q.offer(c);
                seen.add(c);
            }
        }

        while (!q.isEmpty()){
            char cur = q.poll();
            sb.append(cur);

            for (char nei : hash.get(cur)){
                //System.out.println("cur: " + cur + " nei: " + nei + " indegree of nei: " + inDegree.get(nei));
                if (seen.contains(nei)) continue;

                inDegree.put(nei, inDegree.get(nei) - 1);
                if (inDegree.get(nei) == 0){
                    seen.add(nei);
                    q.offer(nei);
                }
            }
        }

        return sb.length() == set.size() ? sb.toString() : "";
    }
}