arrays - 给定一个字符串数组，如果每个字符串都可以连接到其他字符串，则返回 true

Question

给定一个字符串数组，当且仅当所有字符串都可以连接成一条链时才返回 true。

连接的条件是，如果一个字符串的最后一个字符与第二个字符串的第一个字符匹配，则两个字符串可以连接。

示例:String []arr ={"abc", "cde", "cad", "def", "eac"} 将返回 true 因为所有字符串可以连接在一个链中。

"abc"->"cde"->"eac"->"cad"->"def"

另一个例子:String []arr ={"acb", "cde", "def", "ead"} 返回 False 因为
"cde"->"ead"->"def" 是可能的链，但“acb”被排除在外。

注意:不一定要从第一个字符串开始形成链，如果从第一个字符串开始可能会得不到链。如果您从任何其他字符串开始，您可以获得一条链。如果存在可能的链，那么您的解决方案应该返回 true。

在第二个例子中，如果第一个字符串被假设为“fcb”，那么一个可能的链就会存在，"cde"->"ead"->"def "->"fcb" 所以正确。

可能的解决方案(我在想什么):将每个字符串视为一个图形节点，如果条件满足则连接节点。一旦完成，问题就减少到寻找，

如果图中存在哈密顿环，则为 NP-Complete 问题。

有人建议一些算法或任何其他解决方案吗？

Answer 1

您不是在寻找哈密顿循环(即开始 = 开始)，而是哈密顿路径，这也是一个 NP 完全问题。但是，您的图表不是一般图表，因为只有 26 个字母。如果允许超过 26 个字母的符号，那么它实际上等同于哈密顿寻路。

这里有一个解决方案:你应该反过来想:

• 图的顶点是26个字母。
• 对于以x开头以y结尾的每个单词，字母x和y之间有一条边

因此，您得到的实际上是一个多图，因为多个单词可以以同一个字母开头和结尾。那么您所看到的就是所谓的欧拉路径:它是一条使每条边恰好走一次的路径。寻找欧拉路径是一个多项式问题 ( https://en.wikipedia.org/wiki/Eulerian_path )。它实际上可能是历史上第一个图问题。

现引用维基百科:

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

这是一种比搜索哈密顿路径更好的确定是否存在路径的方法。