给定一个字符串数组,当且仅当所有字符串都可以连接成一条链时才返回 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 问题。
有人建议一些算法或任何其他解决方案吗?
最佳答案
您不是在寻找哈密顿循环(即开始 = 开始),而是哈密顿路径,这也是一个 NP 完全问题。但是,您的图表不是一般图表,因为只有 26 个字母。如果允许超过 26 个字母的符号,那么它实际上等同于哈密顿寻路。
这里有一个解决方案:你应该反过来想:
- 图的顶点是26个字母。
- 对于以x开头以y结尾的每个单词,字母x和y之间有一条边
因此,您得到的实际上是一个多图,因为多个单词可以以同一个字母开头和结尾。那么您所看到的就是所谓的欧拉路径:它是一条使每条边恰好走一次的路径。寻找欧拉路径是一个多项式问题 ( https://en.wikipedia.org/wiki/Eulerian_path )。它实际上可能是历史上第一个图问题。
现引用维基百科:
有向图有欧拉轨迹当且仅当至多一个顶点有(出度)-(入度)= 1,至多一个顶点有(入度) − (out-degree) = 1,所有其他顶点的入度和出度都相等,并且其所有非零度的顶点都属于底层无向图的单个连通分量。
这是一种比搜索哈密顿路径更好的确定是否存在路径的方法。
关于arrays - 给定一个字符串数组,如果每个字符串都可以连接到其他字符串,则返回 true,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/17706124/