<h2>警告</h2>
<p>此解决方案适用于按任意顺序排列的字符串列表。</strong></em>这意味着必须检查每对可能的单词是否有公共子字符串,如果字符串列表较大,则可能需要大量内存</p>
<h2>解决方案1允许在需要时连接没有公共子字符串的字</h2>
<pre class="lang-py prettyprint-override"><code>import itertools
from typing import Set, Tuple, Dict, List
def get_match(pair: Tuple[str, str], min_overlap: int = 3) -> str:
a, b = pair
for i in range(min_overlap, min(map(len, pair)) + 1):
if a[-i:] == b[:i]:
return b[:i]
return ""
def links_joiners(strings: List[str]) -> Tuple[Dict[str, str], Set[str]]:
links, joiners = dict(), set()
for pair in itertools.permutations(strings, 2):
if (match := get_match(pair)):
joiners.add(match)
links.update((pair,))
return links, joiners
def get_ordered_strings(strings: List[str], links: Dict[str, str]) -> List[str]:
def find_order(node: str) -> int:
return 0 if node not in links else 1 + find_order(links[node])
return sorted(strings, key=find_order, reverse=True)
def join_strings(strings: List[str], joiners: Set[str]) -> str:
s = "".join(strings)
for j in joiners:
s = s.replace(j, "", 1)
return s
</code></pre>
<p>用法:</p>
<pre class="lang-py prettyprint-override"><code>strings = ["THREEFOUR",
"ONESTRING",
"STRINGTHREE",
"FOURFIVE"]
links, joiners = get_links_and_joiners(strings)
ordered_strings = get_ordered_strings(strings, links)
join_strings(ordered_strings, joiners)
</code></pre>
<p>输出:</p>
<pre class="lang-py prettyprint-override"><code>'ONESTRINGTHREEFOURFIVE'
</code></pre>
<h2>解释</h2>
<p>首先,<code>itertools</code>是标准库的一部分;无需为此解决方案安装任何第三方软件包</p>
<p>现在,<code>links_joiners()</code>函数将获取字符串列表,并查找具有匹配后缀前缀对的所有字符串对,将这些字符串对放入<code>links</code>字典,如下所示:</p>
<pre class="lang-py prettyprint-override"><code>{'ONESTRING': 'STRINGTHREE',
'THREEFOUR': 'FOURFIVE',
'STRINGTHREE': 'THREEFOUR'}
</code></pre>
<p>请注意,这些都不符合顺序。这是因为对于任意的字符串列表,我们首先不能确定字符串是否有序,因此我们必须彻底地迭代<code>strings</code>的每个排列,以确保覆盖了所有对</p>
<p>现在,注意还有一个名为<code>get_ordered_strings()</code>的函数,其中包含一个内部函数<code>find_order()</code>。函数<code>get_ordered_strings()</code>形成了所谓的闭包,但现在理解它并不特别重要。<code>find_order()</code>函数是递归函数,其工作原理如下:</p>
<ol>
<li><p>给定一个<code>node</code>,如果<code>node</code>不是<code>links</code>字典中的一个键,我们已经到达了基本大小写并返回零。否则,请转至步骤2</p>
</li>
<li><p>如果<code>node</code><em>存在,则向该新节点上对<code>find_order</code>的递归调用添加一个</p>
</li>
</ol>
<p>因此,给定一个键,比如<code>"ONESTRING"</code>,<code>find_order()</code>函数将查看与该键关联的值,如果该值也是字典中的键,则查看它的<em>值,依此类推,直到它达到一个不是字典中键的值</p>
<p>下面是<code>find_order()</code>的代码:</p>
<pre class="lang-py prettyprint-override"><code>def find_order(node: str) -> int:
if node not in links:
return 0
return 1 + find_order(links[node])
</code></pre>
<p>下面是调用<code>links_joiners()</code>后<code>links</code>的样子:</p>
<pre class="lang-py prettyprint-override"><code>{'ONESTRING': 'STRINGTHREE',
'THREEFOUR': 'FOURFIVE',
'STRINGTHREE': 'THREEFOUR'}
</code></pre>
<p>现在跟踪对<code>find_order("ONESTRING")</code>的示例调用:</p>
<pre class="lang-py prettyprint-override"><code>find_order("ONESTRING") = 1 + find_order("STRINGTHREE")
= 1 + (1 + find_order("THREEFOUR"))
= 1 + (1 + (1 + find_order("FOURFIVE"))) # Base case
= 1 + (1 + (1 + 0))
= 3
</code></pre>
<p>此函数所做的是查找给定起始字符串可以进行多少成对连接。另一种思考方式是<code>links</code>实际上表示a <a href="https://en.wikipedia.org/wiki/Directed_acyclic_graph" rel="nofollow noreferrer">DAG</a>中的邻接</p>
<p>基本上,我们要做的是获取节点<code>THREEFOUR</code>、<code>ONESTRING</code>、<code>STRINGTHREE</code>、<code>FOURFIVE</code>,并从它们中构造尽可能长的单链表(一种DAG):</p>
<pre class="lang-py prettyprint-override"><code>ONESTRING -> STRINGTHREE -> THREEFOUR -> FOURFIVE
</code></pre>
<p>通过将该图的给定“节点”传递给<code>find_order()</code>,它将一直跟随该图直到结束。所以<code>ONESTRING</code>要走<code>3</code>的距离才能到达终点,而<code>THREEFOUR</code>只走<code>1</code>的距离</p>
<pre class="lang-py prettyprint-override"><code>Node: ONESTRING -> STRINGTHREE -> THREEFOUR -> FOURFIVE
Dist: 3 2 1 0
</code></pre>
<p>现在,通过将<code>find_order</code>传递给内置的<code>sorted()</code>函数,我们可以告诉Python我们希望如何对<code>strings</code>进行排序,在本例中,排序顺序与距离相反。结果是:</p>
<pre class="lang-py prettyprint-override"><code>>>> strings = ['THREEFOUR', 'ONESTRING', 'STRINGTHREE', 'FOURFIVE']
>>> ordered_strings = get_ordered_strings(strings, links)
>>> ordered_strings
['ONESTRING', 'STRINGTHREE', 'THREEFOUR', 'FOURFIVE']
</code></pre>
<p>现在,通过使用公共子字符串连接每个字符串,我们正在构造可能最长的字符串,其中约束条件是每对字符串必须在正确的位置有一个公共子字符串。换句话说,<code>ordered_strings</code>表示DAG中的<em>最长路径</em>。或者更准确地说,我们已经设计了一个具有最长路径的DAG,方法是使用所有提供的节点,并将它们按正确的顺序排列</p>
<p>从这里,我们连接每个字符串:</p>
<pre class="lang-py prettyprint-override"><code>>>> s = "".join(ordered_strings)
>>> s
'ONESTRINGSTRINGTHREETHREEFOURFOURFIVE'
</code></pre>
<p>然后,我们删除每个Joiner的一个实例:</p>
<pre class="lang-py prettyprint-override"><code>for j in joiners:
s = s.replace(j, "", 1)
</code></pre>
<h2>解决方案2,仅连接重叠字符串</h2>
<p>此解决方案重用上面的<code>join_strings()</code>和<code>get_match()</code>。它还使用了walrus操作符<code>:=</code>(python3.8+),但是不用它就可以很容易地编写</p>
<pre class="lang-py prettyprint-override"><code>def join_overlapping_pairs(strings: List[str]) -> str:
if len(strings) == 1:
return strings.pop()
matches = set()
for pair in itertools.permutations(strings, 2):
if (match := get_match(pair)):
matches.add(join_strings(pair, (match,)))
return join_overlapping_pairs(matches)
</code></pre>