Alien Dictionary Problem in Java

外星词典问题 通过分析未知语言中排序的单词列表来确定字符顺序。它根据字符的先决条件构建有向图，检测环以确保存在有效的顺序，并应用拓扑排序来找到正确的字符序列。顶部表单底部表单

问题陈述

给定未知语言中排序的字符串数组和标准字典的前k个字母，目标是确定外星语言中字符的序列。

注意：对于给定的测试用例可能存在多个有效的顺序，因此可以返回任何正确的顺序。如果不可能存在有效的排序，则返回空字符串。

示例 1

输入： arr[] = [“xyz”, “xwz”, “xwy”, “wxy”], k = 4

输出： x z y w

解释

• “xyz”和“xwz”表明“y”出现在“w”之前。
• “xwz”和“xwy”表明“z”出现在“y”之前。
• “xwy”和“wxy”表明“x”出现在“w”之前。
• 因此，[‘x’, ‘z’, ‘y’, ‘w’] 是一个有效的排序。

示例 2

输入： arr[] = [“rat”, “cat”, “bat”], k = 3

输出： r c b

解释

• “rat”和“cat”表明“r”出现在“c”之前。
• “cat”和“bat”表明“c”出现在“b”之前。
• 因此，[‘r’, ‘c’, ‘b’] 是一个有效的排序。

示例 3

输入： arr[] = [“apple”, “apricot”, “banana”], k = 6

输出： p r a b l e n

解释

• “apple”和“apricot”表明“p”出现在“r”之前。
• “apricot”和“banana”表明“a”出现在“b”之前。
• 其余字母的顺序保持不变。
• 因此，[‘p’, ‘r’, ‘a’, ‘b’, ‘l’, ‘e’, ‘n’] 是一个有效的排序。

问题的解决方案

步骤 1： 比较连续的单词，创建一个有向图，其中边表示字符的先决条件。

步骤 2： 采用深度优先搜索（DFS）来识别循环，确认序列是合法的且可行的。

步骤 3： 使用 DFS 探索图，按正确的顺序将节点压入栈。

步骤 4： 从栈中弹出元素以获取正确的字符序列。

步骤 5： 打印计算出的字符顺序，表示外星语言的字母顺序。

让我们在 Java 程序中实现上述步骤。

输出

 
Character order: cab   

时间复杂度： 图的构建、循环检测和拓扑排序为 O(N * M + K)。

辅助空间： 图为 O(K²)，递归、访问数组和输出为 O(K)。