Alien Dictionary

AlienDictionary.java

public String alienOrder(String[] words) {
        if (words == null || words.length == 0) {
            return "";
        }
        // adjacency list
        Map<Character, List<Character>> graph = new HashMap<>();
        // for topology sort
        Map<Character, Integer> inDegree = new HashMap<>(); 
        
        // WRONG 2: still populate the graph and inDegree, or NLE in the topology sort later
        // and it has to populate before here, or the "break" will have something missed
        for (String word : words) {
            for (char c : word.toCharArray()) {
                graph.put(c, graph.getOrDefault(c, new ArrayList<>()));
                inDegree.put(c, inDegree.getOrDefault(c, 0));
            }
        }
        
        for (int i = 0; i < words.length - 1; i++) {
            String word1 = words[i];
            String word2 = words[i + 1];
            
            // edge case, just for OJ
            if (word1.length() > word2.length() && word1.startsWith(word2)) {
                return "";
            }
            
            for (int j = 0; j < Math.min(word1.length(), word2.length()); j++) {
                char c1 = word1.charAt(j);
                char c2 = word2.charAt(j);
                if (c1 != c2) {
                    // update graph
                    graph.get(c1).add(c2);
                    // update inDegree
                    inDegree.put(c2, inDegree.getOrDefault(c2, 0) + 1);
                    // WRONG 1: break after first different, to avoid additional coutn for inDegree
                    break;
                }
            }
        }
        
        // complete graph build, start the topology sort
        StringBuilder sb = new StringBuilder();  // store temp result
        Deque<Character> queue = new ArrayDeque<>();
        for (Map.Entry<Character, Integer> entry : inDegree.entrySet()) {
            if (entry.getValue() == 0) {
                queue.offer(entry.getKey());
            }
        }
        
        while (!queue.isEmpty()) {
            char curr = queue.poll();
            sb.append(curr);
            for (char neighbor : graph.get(curr)) {
                inDegree.put(neighbor, inDegree.get(neighbor) - 1);
                if (inDegree.get(neighbor) == 0) {
                    queue.offer(neighbor);
                }
            }
        }
        
        return sb.length() == inDegree.size() ? sb.toString() : "";
        
    }