算法:是否可以形成一个有效的字符串

Question

假设我们有 n 个三个字母的子串。通过连接这些 N 个子字符串(其中重叠的字母只写一次)，可以从这 N 个子字符串中生成一个长度为 n+2 的字符串。因此该字符串必须具有 a1,a2,a3,a4... 的形式

因此，仅当两个子字符串在两个相邻位置重叠时才允许链接它们: 'yxz' + 'xzw' = 'yxzw' ，但 'yxz' + 'aby' 是不允许的。

示例 1:n = 3 个三个字母的子串是 'abc','cde','bcd' 输出:是.因为 'abc' + 'bcd'+ 'cde' = 'abcde' 是 n+2 = 5 个字母的有效字符串。

示例 2:n = 3 个三个字母的子串是 'abc','bca','bcd' 输出:NO。因为不可能将它们全部连接起来。

我怎样才能找到一个有效的算法来解决这个问题？尝试所有可能的组合花费的时间太长，复杂度为 O(n!)

Answer 1

解决此类问题的一种流行方法是构建输入序列的重叠图，其顶点是您的三元组，其中两个三元组之间的弧 a_i -> a_j 意味着a_i的最后两个字母是a_j的前两个字母；然后找一个Hamiltonian path在结果图中。

简单的搜索当然不会胜过您提到的详尽搜索，但链接的维基百科文章提供了一些关于如何更有效地执行此操作的线索。