269. Alien Dictionary (Hard)

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

Solution 1: BFS, Topological Sort O(n * L); O(|V|+|E|) = O(26 + 26^2) = O(1)

    /**
     * Graph. Topological Sort. BFS.
     * Two steps:
     * 1) Build a graph and in-degree from the given words.
     * 2) Do topological sort.
     * <p>
     * Topological sort based on Kahn's algo.
     * It needs a graph and each node's in-degree.
     * Then start with all 0 in-degree nodes, enqueue them.
     * While the queue is not empty, dequeue a node and add to result order.
     * Remove edges start from this node by reducing the in-degree of its neighbors.
     * If those nodes become 0 in-degree as well, enqueue.
     * When queue is empty, it's done.
     * Before return, check if the order is valid by comparing the result length with # of graph nodes.
     */
    public String alienOrder(String[] words) {
        if (words == null || words.length == 0) {
            return "";
        }

        Map<Character, Integer> inDegrees = new HashMap<>();
        for (String s : words) { // Init in-degree of all characters given to 0.
            for (char c : s.toCharArray()) {
                inDegrees.put(c, 0);
            }
        }

        Map<Character, Set<Character>> graph = new HashMap<>(); // Use set to avoid duplicate edge.
        for (int i = 0; i < words.length - 1; i++) { //遍历单词数组
            String w1 = words[i];
            String w2 = words[i + 1];
            if (w1.startsWith(w2) && w1.length() > w2.length()) { // "abcee" -> "abc", invalid.
                return "";
            }
            for (int j = 0; j < w1.length() && j < w2.length(); j++) { //遍历单词String
                char c1 = w1.charAt(j);
                char c2 = w2.charAt(j);
                if (c1 != c2) {
                    if (!graph.containsKey(c1)) {
                        graph.put(c1, new HashSet<>());
                    }
                    if (graph.get(c1).add(c2)) {
                        inDegrees.put(c2, inDegrees.get(c2) + 1);
                    }
                    break; // Should break once one edge is found.
                }
            }
        }

        Queue<Character> queue = new LinkedList<>();
        for (Map.Entry<Character, Integer> e : inDegrees.entrySet()) {
            if (e.getValue() == 0) queue.offer(e.getKey());
        }
        StringBuilder order = new StringBuilder();
        while (!queue.isEmpty()) {
            char n = queue.poll();
            order.append(n);
            // Remove edges from graph by updating in degrees of neighbors.
            if (graph.containsKey(n)) { // Avoid NPE.
                for (char neighbor : graph.get(n)) {
                    inDegrees.put(neighbor, inDegrees.get(neighbor) - 1); // Update in degree.
                    if (inDegrees.get(neighbor) == 0) { // Add 0 in degree node to queue.
                        queue.offer(neighbor);
                    }
                }
            }
        }
        return order.length() == inDegrees.size() ? order.toString() : ""; // Check if all nodes are in result.
    }