LeetCode外星词典问题两处疑问求技术澄清

疑问1：推导得'n'应在'f'之前，为何"rfnn"是有效的？ #

我们推导的n < f是字母间的顺序约束，这个约束仅用于判断不同单词之间的排序是否符合外星词典规则，和单个单词内部的字符排列无关。

看示例里的rfnn，它的前序单词是enn，两者第一个不同字符是e和r，根据推导的顺序e < r，enn < rfnn完全符合排序规则。而rfnn内部n在f前面只是单词本身的拼写，这和n < f的约束不冲突——该约束仅要求：如果两个单词在某一位置出现n和f的差异，那么n所在单词必须排在f所在单词之前，并不限制单个单词内的字符顺序。

疑问2：题目提到可能存在多个有效顺序，原因是什么？ #

当部分字母之间没有明确的先后约束关系时，这些字母的相对顺序可以自由调整，只要满足已有的约束即可，由此会产生多个有效顺序。

举个例子：若输入单词列表为["ac", "bc"]，仅能推导出a < b，但字符c与a、b之间无任何约束（没有单词对在某一位置出现c与a/b的差异）。此时有效的字母顺序可以是acb、cab（只要保证a在b之前，c可放在任意位置）。

再比如，若推导得到的约束是a < b、a < c，但b和c之间没有约束，那么abc、acb都是符合要求的有效顺序。

内容的提问来源于stack exchange，提问作者234