Google面试题（四）

26个英文字母从新排序（未知的顺序alphabet），然后用这个位置的顺序给一组数据(array list)排序现在给你这组array list，问能不能计算出来那个alphabet未知的顺序。

思路：拓扑排序就行

0. 初始排序图[G]为单个点[0]，[0]小于任何字母（添加[0]为了保证图的连通性，编
程简单），[G]为有向图。
1. 对于输入array [A]，取每个串第一个字母，去重复，得到一个有序序列[T]。将这
个串merge到排序图中，merge的方法：
a.对[T]每个字母[a_i]，如果在[G]中没有存在，则添加到[G]中。若[a_i]为[T]中
第一个字母，则添加边[a_i]->[0]，否则添加边[a_i]->[a_i-1]。
b. 如果[a_i]在[G]中已经存在，若边[a_i]->[a_i-1]（对于[a_0]为[a_0]->[0]）
不存在，添加此边。
2. 对于首字母相同的[A]中的串，去掉首字母后组成新的array [A]', 如果有空串，在
空串处splitarray。 递归调用步骤1.

结果生成：
1. 如果[G]中存在回路，输入有矛盾，无解
2. 如果[G]中的字母节点小于26个，或者存在环（除1情况外），产生不唯一的解。
3. 如果[G]是一条含有26个节点的无环路径，产生唯一解。