rog*_*hat 8 arrays string algorithm data-structures
您将获得一个字符串数组,当且仅当所有字符串都可以在一个链中连接时才返回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.
在第二个例子中,如果假设第一个String “fcb”,则可能存在一个链,"cde"->"ead"->"def"->"fcb"因此为True.
可能的解决方案(我在想什么):将每个字符串视为一个图节点,并在条件满足时连接节点.一旦完成,问题就会减少,
if there exists a Hamiltonian Cycle in a graph,这是NP完全问题.
有人建议一些算法或任何其他解决方案？
你不是在寻找汉密尔顿循环(即,开始=开始),而是哈密顿路径,这也是一个NP完全问题.但是,由于只有26个字母,因此您的图表不是一般图表.如果你允许更多的符号而不是26个字母,那么它实际上相当于汉密尔顿路径发现.
这是一个解决方案:您应该以相反的方式思考:
因此,你得到的实际上是一个多图,因为几个单词可以以相同的字母开头和结尾.然后你所看到的被称为欧拉路径:它是一条路径,每条边都恰好一次.寻找欧拉路径是一个多项式问题(https://en.wikipedia.org/wiki/Eulerian_path).它实际上可能是历史上第一个图形问题之一.
现在引用维基百科:
当且仅当最多一个顶点具有(out-degree) - (in-degree)= 1时,有向图具有欧拉轨迹,最多一个顶点具有(度数) - (out-degree)= 1,每个其他顶点具有相等的in-degree和out-degree,并且所有具有非零度数的顶点都属于底层无向图的单个连通分量.
这是一种更好的方法来决定是否存在路径而不是搜索哈密尔顿路径.