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 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:

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

Output: "wertf"

Example 2:

Input:
[
  "z",
  "x"
]

Output: "zx"

Example 3:

Input:
[
  "z",
  "x",
  "z"
] 

Output: "" 

Explanation: The order is invalid, so return "".

Note:


Solution:

class Solution {
    public String alienOrder(String[] words) {
        Map<Character, Set<Character>> edges = new HashMap<>();
        Map<Character, Set<Character>> inDegrees = new HashMap<>();
        for (int i = 0; i < words.length; i ++) {
            String word = words[i];
            for (char c : word.toCharArray()) {
                edges.put(c, edges.getOrDefault(c, new HashSet<>()));
                inDegrees.put(c, inDegrees.getOrDefault(c, new HashSet<>()));
            }
            if (i > 0) {
                String lastWord = words[i - 1];
                if (word.length() < lastWord.length() && lastWord.startsWith(word)) {
                    return "";
                }
                int len = Math.min(lastWord.length(), word.length());
                for (int k = 0; k < len; k ++) {
                    if (lastWord.charAt(k) == word.charAt(k)) {
                        continue;
                    }
                    char curr = word.charAt(k);
                    Set<Character> parents = inDegrees.getOrDefault(curr, new HashSet<>());
                    parents.add(lastWord.charAt(k));
                    inDegrees.put(curr, parents);
                    Set<Character> neis = edges.getOrDefault(lastWord.charAt(k), new HashSet<>());
                    neis.add(curr);
                    edges.put(lastWord.charAt(k), neis);
                    break;
                }
            }
        }
        StringBuilder sb = new StringBuilder();
        Deque<Character> queue = new ArrayDeque<>();
        Set<Character> visited = new HashSet<>();
        for (Map.Entry<Character, Set<Character>> entry : inDegrees.entrySet()) {
            if (entry.getValue().size() == 0) {
                char c = entry.getKey();
                queue.offer(c);
                visited.add(c);
            }
        }
        while (!queue.isEmpty()) {
            char c = queue.poll();
            sb.append(c);
            for (char n : edges.get(c)) {
                inDegrees.get(n).remove(c);
                if (inDegrees.get(n).size() == 0 && visited.add(n)) {
                    queue.offer(n);
                }
            }
        }
        if (sb.length() == edges.size()) {
            return sb.toString();
        }
        return "";
    }
}