Google面试题求解:26个英文字母从新排序(未知的顺序alphabet),然后用这个位置的顺序给一组数据(array list)排序现在给你这组array list,问能不能计算出来那个alphabet未知的顺序。

已邀请:

木舟

赞同来自: 数美招聘 Eric_Jiang

**思路:**
 
拓扑排序就行 

初始排序图为单个点,小于任何字母(添加为了保证图的连通性,编程简单),为有向图。  
对于输入array ,取每个串第一个字母,去重复,得到一个有序序列。将这个串merge到排序图中,merge的方法:

a.对每个字母,如果在中没有存在,则添加到中。若为中第一个字母,则添加边->,否则添加边->。  
b. 如果在中已经存在,若边->(对于为->)不存在,添加此边。


对于首字母相同的中的串,去掉首字母后组成新的array ', 如果有空串,在空串处splitarray。 递归调用步骤1.    

 
**结果生成: **
1. 如果中存在回路,输入有矛盾,无解 
2. 如果中的字母节点小于26个,或者存在环(除1情况外),产生不唯一的解。 
3. 如果是一条含有26个节点的无环路径,产生唯一解。

要回复问题请先登录注册