Description

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

Topological sort, time O(mn) m is words count, n is avg word len, space O(1)

想了一会儿发现就是拓扑排序啊。用常规的拓扑排序解法即可，特别需要注意的是，indegree数组要初始化为-1，然后需要遍历words，将出现的character对应的indegree设置成0。只有这样，最后在做拓扑排序的时候，才只会把words中出现过的character加到queue中，否则最后返回的字符串会包含所有26个字符...

想想看为什么之前写拓扑排序的时候，没有注意到indegree的初始化问题，因为之前遇到的题目都是这样描述的：

There are a total of n courses you have to take, labeled from 0 to n - 1.

那么也就是说，题目保证了[0, n)取值的完整性，indegree的确该全部初始化成0。

但是Alien Dictionary这道题不一样了，words中可能只出现了某些character，所以需要特别初始化indegree才行。切记！

class Solution {
    public String alienOrder(String[] words) {
        Map<Character, Set<Character>> graph = new HashMap<>();
        Map<Character, Integer> indegree = new HashMap<>();
        // initialize graph and indegree to avoid NPE
        for (String word : words) {
            for (char c : word.toCharArray()) {
                if (graph.containsKey(c)) {
                    continue;
                }
                graph.put(c, new HashSet<>());
                indegree.put(c, 0);
            }
        }
        
        for (int i = 0; i < words.length - 1; ++i) {
            String curr = words[i];
            String next = words[i + 1];
            for (int j = 0; j < Math.min(curr.length(), next.length()); ++j) {
                char x = curr.charAt(j);
                char y = next.charAt(j);
                
                if (x != y) {
                    if (graph.get(x).add(y)) {
                        indegree.put(y, indegree.get(y) + 1);
                    }
                    
                    break;
                }
                
            }
        }
        // topological sort
        StringBuilder sb = new StringBuilder();
        Queue<Character> queue = new LinkedList<>();
        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 next : graph.get(curr)) {
                indegree.put(next, indegree.get(next) - 1);
                if (indegree.get(next) == 0) {
                    queue.offer(next);
                }
            }
        }
        // don't forget to check if it's valid
        return sb.length() < indegree.size() ? "" : sb.toString();
    }
}