269. Alien Dictionary

class Solution {

    public String alienOrder(String[] words) {
        Map<Character, List<Character>> graph = new HashMap<>(); // We cannot use a set here
        Map<Character, Integer> indegree = new HashMap<>();

        for (int i = 0; i < words.length; i++) {
            for (int j = 0; j < words[i].length(); j++) {
                Character c = words[i].charAt(j);
                if (!indegree.containsKey(c)) {
                    indegree.put(c, 0);
                }
            }
        }

        for (int i = 0; i < words.length; i++) {
            if (i != words.length - 1) {
                String word1 = words[i];
                String word2 = words[i + 1];
                if (word1.length() > word2.length() && word1.startsWith(word2)) {
                    return "";
                }
                int length = Math.min(word1.length(), word2.length());
                for (int j = 0; j < length; j++) {
                    if (word1.charAt(j) != word2.charAt(j)) {
                        indegree.put(word2.charAt(j), indegree.get(word2.charAt(j)) + 1);
                        if (graph.containsKey(word1.charAt(j))) {
                            List<Character> cur = graph.get(word1.charAt(j));
                            cur.add(word2.charAt(j));
                            graph.put(word1.charAt(j), cur);
                        } else {
                            List<Character> cur = new ArrayList<>();
                            cur.add(word2.charAt(j));
                            graph.put(word1.charAt(j), cur);
                        }
                        break; // rest comparision is meaningless
                    }
                }
            }
        }

        Deque<Character> queue = new LinkedList<>();
        StringBuilder sb = new StringBuilder();

        for (Map.Entry<Character, Integer> entry : indegree.entrySet()) {
            char c = entry.getKey();
            int count = entry.getValue();
            if (count == 0) {
                sb.append(c);
                queue.offer(c);
            }
        }

        while (!queue.isEmpty()) {
            char cur = queue.poll();
            List<Character> subs = graph.get(cur);
            if (subs != null) { // important
                for (char c : subs) {
                    indegree.put(c, indegree.get(c) - 1);
                    if (indegree.get(c) == 0) {
                        sb.append(c);
                        queue.offer(c);
                    }
                }
            }
        }

        for (Map.Entry<Character, Integer> entry : indegree.entrySet()) {
            int count = entry.getValue();
            if (count != 0) {
                return "";
            }
        }

        return sb.toString();
    }
}