[LeetCode]Alien Dictionary

又是topological sorting的问题，但是这一题主要是建图比较麻烦。顶点就是每一个字母，edge从给定的 lexicographically sort里可以推断出来，我们首先比较首字母会得到一个序列，之后对于前缀相同的我们递归地比较之后的字母，直到比较完所有的后缀。之后根据这些序列来建图。之后就是普通的topological sorting了，假设字符不限于26个字母，有n个单词，平均长度k，时间复杂度O(V + E) = O(n * k + n * k) = O(n * k)，空间复杂度O(V + E) = O(n * k + n * k) = O(n * k)，代码如下：