gpt4 book ai didi

python - 排列字符串以获得最大重叠

转载 作者:塔克拉玛干 更新时间:2023-11-03 03:00:18 25 4
gpt4 key购买 nike

假设我有这组字符串:

strings = {'qqq', 'eqq', 'qqw', 'www', 'qww', 'wwe', 'eee', 'eeq', 'wee', 'qwe'}

如何编写一种算法来排列字符串,使它们最大程度地重叠?我已经知道一种排列方式如下:

qww
www
wwe
wee
eee
eeq
eqq
qqq
qqw
qwe

然而,我发现上述结果是用暴力破解的。有更聪明的方法吗?

最佳答案

这称为最短超弦问题,是 NP 完全问题。

您可能对论文 Approximation Algorithms for the Shortest Common Superstring Problem by Jonathan Turner 中的方法感兴趣.

关于python - 排列字符串以获得最大重叠,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/18110475/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com