找出随机单词是否构成由最后一个和第一个字母（单词足球）连接的单词序列

Question

所以我这里有问题。我得到一组随机单词，我的工作是找出是否存在至少一个连接所有单词（首尾字母）的单词序列。例如，单词序列（苹果 - 鹰 - 大象 - 老虎）将返回 true。但是单词序列（苹果 - 鹰 - 大象 - 桃子）会返回假。所以我想使用一些图论。我发现我可以创建有向图并强制它找到图中最长的路径或汉密尔顿路径。这里的问题是图可以是循环的，所以问题总是 NP full。它真的是最好的解决方案还是我错过了什么而问题实际上要容易得多？最好的显然是有无环图，这样我就可以使用关键路径算法在 o(n+m) 中找到解决方案。蛮力真的是我唯一的选择还是有其他替代方法来解决这个问题？起初我想到了一些事情，比如计算开始和结束的字母，然后比较它们，但它有其自身的问题，我无法真正解决它们。无论如何，如果蛮力是我唯一的选择，有没有什么好的方法可以尽可能地优化最长路径算法？

Answer 1

好吧，让我试一试。首先，我假设这个问题的输入类似于有限长度字符串（单词）的有限集S（不是多集），带有字母 [az]（小写）。我们假设 | 小号|> = 2，并且对于每个瓦特在小号：| W |> = 2。假设我们表示一个词w属于集合S。此外，我们将提取给定单词w的第一个字符的函数表示为f；同样，我们将提取给定单词w的最后一个字符的函数表示为l。例如，对于w ="hello", f ( w)="h" 和l ( w )="o"。我们假设在S中不存在两个词w , w'使得f ( w )= f ( w' ) 和l ( w )= l ( w' )，这是为了避免具有相同源目的地的多个边（这对游戏来说是一个公平的假设吗？）。无论如何，检查没有两个单词共享相同的第一个和最后一个字母可以在O ( S ) 时间内完成，与单词数成线性关系。

我们将集合S转换为有向图（有向图）G =( V , E )。平凡，我们首先同时设置V和Ë为空集，则对每个字瓦特在小号：V = V ∪{ ˚F（瓦特）} U {升（瓦特）}，和Ë = È ∪{（˚F（瓦特), l ( w ))}。前面的过程在输入大小的线性时间内运行 | 小号| = | 乙| （重要提示：单词数等于边数）。

现在，这就是事情开始变得有趣的地方。要“连接”每个单词，您必须遍历一条仅使用每个边一次的路径（单词是边，字母是顶点）；这不是哈密顿路径，而是欧拉路径！一个有向图包含欧拉路径存在充要条件。存在性检查可以在线性时间内完成 wrt |V| （来自原始词集S的不同的第一个和最后一个字母）。此外，欧拉路径的推导可以在O (| V |+| E |) 中完成（在最坏的情况下 | E | 支配 | V |，因此与集合S 中的单词数成线性关系）。

一种算法来解决这个问题。该算法基于Hierholzer 算法，如果您不想阅读论文，可以在此处找到一些信息。这是我收集/修改的算法：

//Start the existence check & initial node selection

Compute the vertices in-degrees and out-degrees.

If all vertices have the same out-degree as in-degree, then set *v*0 to any vertex of the graph.

Else If at most one vertex has out-degree - in degree = 1 & at most one vertex has in-degree - out-degree = 1, then set *v*0 to the vertex whose out-degree - in degree = 1.

Else there is no Euler path 

//Use two stacks to compute the Eulerian path using Hierholzer\'s algorithm

HEAD and TAIL both stacks empty.

Push *v*0 to HEAD.

While HEAD != empty

    While out-degree of top of stack vertex, *u* > 0

        Let *v* be a vertex neighbor of *u* (the edge (*u*, *v*) exists in *G*).

        Push *v* to HEAD. //*v* becomes new *u*

        Delete edge (*u*,*v*) from *G*

        Decrease the out-degree of *u*

    end while.

    While HEAD != empty and top vertex *u* of HEAD out-degree == 0

        Pop *u* from HEAD and Push it to TAIL

    end while.

end while.

The Eulerian path is found in order in TAIL

现在，您需要从TAIL. 应该有| E | - 1 个元素，重建边缘应该是微不足道的。为了得到单词，因为没有两个单词共享相同的首尾字母，所以边和单词之间是一一对应的。如果之前存储在哈希表中，检索词序可以在线性时间内完成 乙|。

好的，那么解决这个问题的步骤和复杂性： 1. 将S转换为图G , O (| S |)。2. 验证解O (| S |) 的存在性。3. 导出解O (| S |)。4. 检索词序，O (| S |)。

一般情况下，您可以根据O (| S |) 中的假设来解决此任务。

这是一项有趣的任务。你从哪里得到的？

Answer 2

只有存在以单词的最后一个字符开头的每个单词，除了最后一个单词的一个例外，序列才是可能的。一个可能的解决方案是构建一个包含每个单词的首尾字符的哈希映射并检查它是否满足该属性，一定要在处理一次后标记一个单词，以免再次迭代。