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

木舟

赞同来自: 数美招聘 Eric_Jiang

思路:   拓扑排序就行 
  1. 初始排序图[G]为单个点[0],[0]小于任何字母(添加[0]为了保证图的连通性,编程简单),[G]为有向图。  
  2. 对于输入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])不存在,添加此边。
  3. 对于首字母相同的[A]中的串,去掉首字母后组成新的array [A]', 如果有空串,在空串处splitarray。 递归调用步骤1.    
  结果生成:  1. 如果[G]中存在回路,输入有矛盾,无解  2. 如果[G]中的字母节点小于26个,或者存在环(除1情况外),产生不唯一的解。  3. 如果[G]是一条含有26个节点的无环路径,产生唯一解。

要回复问题请先登录注册