我最近被问到以下面试问题:
你有一个用外来语写的字典页面.假设该语言与英语类似,并且从左到右读/写.此外,单词按字典顺序排列.例如,页面可以是:ADG,ADH,BCD,BCF,FM,FN
您必须提供页面中存在的字符集的所有词典排序.
我的方法如下:A的优先级高于B,G的优先级高于H.因此,我们有关于某些字符的排序的信息:
A->B, B->F, G->H, D->F, M->N
可能的排序可以是ABDFGNHMC,ACBDFGNHMC,......我的方法是使用数组作为位置持有者并生成所有排列以识别所有有效排序.最糟糕的情况是时间复杂度为N!其中N是字符集的大小.我们能比蛮力方法做得更好吗？
提前致谢.