擅长:python、mysql、java
<p>要确定两个字符串<code>a</code>和<code>b</code>的重叠,可以检查<code>b</code>的前缀是否是<code>a</code>的后缀。然后,您可以在一个简单的循环中使用该检查,聚合结果并根据重叠对列表中的下一个字符串进行切片。在</p>
<pre><code>lst = ['SGALWDV', 'GALWDVP', 'ALWDVPS', 'LWDVPSP', 'WDVPSPV']
def overlap(a, b):
return max(i for i in range(len(b)+1) if a.endswith(b[:i]))
res = lst[0]
for s in lst[1:]:
o = overlap(res, s)
res += s[o:]
print(res) # SGALWDVPSPV
</code></pre>
<p>或使用<code>reduce</code>:</p>
^{pr2}$
<p>这可能不是超高效的,复杂度大约为O(nk),n是列表中的字符串数,k是每个字符串的平均长度。只需测试<code>b</code>的假定重叠的最后一个字符是否是<code>a</code>的最后一个字符,从而减少生成器表达式中字符串切片和函数调用的数量,从而提高效率:</p>
<pre><code>def overlap(a, b):
return max(i for i in range(len(b)) if b[i-1] == a[-1] and a.endswith(b[:i]))
</code></pre>