algorithm - 由列表中的单词组成的单词链

Question

我被困在一个编程问题上。我需要帮助!问题如下。给定一个单词列表，如果可以按如下方式创建单词链，我必须返回 true。

cat tab bat 等，即一个词的结尾字母必须是链中另一个词的开头。
我应该如何实现这个？
我只能想到暴力解决方案，我生成一个列表的所有排列，然后检查是否有任何排列满足条件。谢谢。

Answer 1

考虑一个有向图，每个字母都有一个顶点，每个单词都有一个边。

所以单词“cat”对应于从顶点“c”到顶点“t”的有向边。

在此图中，您试图查看是否存在 Eulerian path .

可以按照 wiki 页面上的描述检查欧拉路径:

A directed graph has an Eulerian trail if and only if at most one vertex has (out-degree) − (in-degree) = 1, at most one vertex has (in-degree) − (out-degree) = 1, every other vertex has equal in-degree and out-degree, and all of its vertices with nonzero degree belong to a single connected component of the underlying undirected graph.

例子

在这张图中，我们可以通过“c”->“t”->“b”->“t”遍历所有边。

这是一条欧拉路径(它沿着所有边行进)，对应于单词 cat、tab、bat。