从给定的排序字典中查找优先级字符

问题陈述

你得到了一个按字典顺序排序的字符串数组。你的任务是确定此数组中使用的字符顺序。

例如

在上面的例子中，字符的顺序将是 b、d、a、c

因此，我们必须以字符串的形式打印字符的字典序。

方法

为了解决这个问题，我们将一次比较两个单词，并且不匹配的字符将决定字符的顺序。

例如，我们将比较 "baa" 和 "abcd"。

两个字符串的索引 0 不同，所以我们可以说 b 会排在 a 之前，而其他字符的顺序我们无法确定。

我们将创建一个字符的有向图，然后打印拓扑排序顺序以获得我们的答案。

例如

在上面的例子中，我们将一次比较两个相邻的字符串并尝试创建一个图。

对于 i=0 和 i=1

我们有 "baa" 和 "abcd"，不匹配的字符是 b、a。所以可以肯定的是 b 会在 a 之前，并且会有一条从 b 到 a 的边。

对于 i=1 和 i=2

我们有 "abcd" 和 "abca"，第一个不匹配的字符是 'd' 和 'a'，所以会有一条从 d 到 a 的边。

现在图将看起来像这样

对于 i=2 和 i=3，我们有字符串 "abca" 和 "cba"，所以第一个不匹配的字符是 'a' 和 'c'，所以它们将绘制一条从节点 a 到节点 c 的边。

图将是

对于 i=3 和 i=4，我们有 "cab" 和 "cad"，所以不匹配的字符是 'b' 和 'd'。现在会有一条从 'b' 到 'd' 的边，并且两者都有指向 'a' 的边。所以我们将像这样修改图

现在，在完成整个迭代之后，我们将得到这个图的拓扑排序顺序，即 "bdac"，这将是我们的答案。

Java 代码

输出

说明

在上面的代码中，我们有一个函数，它以字符串形式返回答案，我们正在打印结果。我们使用一个字符与 HashSet 的哈希映射，其中对于每个唯一的字符，我们将它的邻居存储到 HashSet 中。

我们使用了另一个字符与整数的哈希映射来存储特定字符的入度（传入边的数量）。

最初，我们将所有字符的入度存储为 0。

现在我们正在迭代字符串数组从索引 0 到索引 n-2，并比较两个相邻的字符串。

对于字符串，我们将逐字符迭代，如果两个字符串在相同索引处的字符不匹配，则我们将停止。

现在我们检查图是否包含字符串 1 的字符。如果图不包含字符 1，那么我们将它添加到图中，并且我们将字符 2 作为其邻居放入字符 1 的 HashSet 中。

此外，我们将字符 2 的入度增加 1。

在创建图和字符的入度之后，我们将获得图的拓扑排序。

我们将使用 Kahn 算法以广度优先搜索顺序获取拓扑排序顺序。我们将使用队列并放入所有入度为零的字符。现在我们将迭代队列直到它不为空。

每次，我们都会从队列中移除顶部元素并将其添加到我们的答案中。我们将访问它的邻居并将其入度减 1。如果任何邻居的入度等于零，我们将其添加到队列中。

因此我们将获得拓扑排序顺序。

时间复杂度： O(N*L)，其中 N 是数组的长度，L 是字符串的最大长度。

空间复杂度： O(N*L)