algorithm - Chain of words made by words in the list

Question

I am stuck at a programming question. I need help! The question is as follows. Given a list of words I have to return true if it is possible to create a chain of words as follows.

cat tab bat etc. i.e end letter of a word has to be start of the other in the chain.
How should I implement this?
I can only think of the brute force solution where I generate all permutations of a list and then check if any of it meets the conditions. Thanks.

Answer 1

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

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

在此图中，您试图查看是否存在欧拉路径。

可以按照 wiki 页面上的说明检查欧拉路径：

有向图有欧拉轨迹当且仅当至多一个顶点有 (out-degree) - (in-degree) = 1，至多一个顶点有 (in-degree) - (out-degree) = 1，每其他顶点具有相等的入度和出度，并且其所有具有非零度的顶点都属于底层无向图的单个连通分量。

例子

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

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