假设我们有 n 个三字母子串。通过连接这 N 个子串，可以将它们组成长度为 n+2 的字符串(其中重叠的字母仅写入一次)。其中该字符串必须具有 a1,a2,a3,a4... 的形式
因此，仅当两个子字符串在两个相邻位置重叠时才允许链接它们: 'yxz' + 'xzw' = 'yxzw' ，但例如 'yxz' + 'aby' 是不允许的。
示例 1:n = 3 个三字母子串为 'abc','cde','bcd' 输出:YES 。因为 'abc' + 'bcd'+ 'cde' = 'abcde' 是一个包含 n+2 = 5 个字母的有效字符串。
示例 2:n = 3 个三字母子串为 'abc','bca','bcd' 输出:NO。因为不可能将它们全部连接起来。
如何找到解决此问题的有效算法？尝试所有可能的组合花费的时间太长，O(n!)
最佳答案
解决此类问题的流行方法之一是构建输入序列的重叠图，其顶点是三元组，并且两个三元组之间的弧 a_i -> a_j 意味着a_i 的最后两个字母是 a_j 的前两个字母；然后找到Hamiltonian path在结果图中。
简单的搜索当然不会优于您提到的详尽搜索，但链接的维基百科文章提供了一些关于如何更有效地执行此操作的线索。
关于算法:是否有可能形成一个有效的字符串，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/55063593/