如何将字符串列表连接起来并删除重复字母（保持它们连续）

Question

我的列表：

l = ["volcano", "noway", "lease", "sequence", "erupt"]

期望的输出：

'volcanowayleasequencerupt'

我的尝试：

使用 itertools.groupby，但当有连续 2 个重复字母时似乎不起作用（例如：leasesequence -> sese 保留）：

>>> from itertools import groupby
>>> "".join([i[0] for i in groupby("".join(l))])
'volcanonowayleasesequencerupt'

正如您所看到的，它只删除了最后一个 'e'，这并不理想，因为如果一个字母有双字符，它们将被缩小为1个。 例如:'suddenly'会变成'sudenly'。

我正在寻找最Pythonic的方法。

提前谢谢。

编辑

我的列表中没有重复项。

- hofD

---

在列表 l = ['split', 'it', 'lit'] 中，第三个单词与第二个单词相比匹配得更远，你对此有什么期望？ - Kelly Bundy

@HeapOverflow 我期望得到 'splitlit'。 - hofD

那么规则就是通过与直接前面的单词重叠来裁剪每个单词？ - Kelly Bundy

@HeapOverflow 是的，就像这样。 - hofD

这能帮助吗？https://dev59.com/SV4c5IYBdhLWcg3wM3-R - Clément

Answer 1

使用一个帮助函数，通过删除单词 t 的最长前缀来裁剪它，该前缀也是字符串 s 的后缀:

def crop(s, t):
    for k in range(len(t), -1, -1):
        if s.endswith(t[:k]):
            return t[k:]

接着，将每个词与它前面的词一起裁剪：

>>> l = ["volcano", "noway", "lease", "sequence", "erupt"]
>>> ''.join(crop(s, t) for s, t in zip([''] + l, l))
'volcanowayleasequencerupt'

>>> l = ['split', 'it', 'lit']
>>> ''.join(crop(s, t) for s, t in zip([''] + l, l))
'splitlit'

- Kelly Bundy

Answer 2

在我看来，更易读的版本：

from functools import reduce


def max_overlap(s1, s2):

    return next(
        i
        for i in reversed(range(len(s2) + 1))
        if s1.endswith(s2[:i])
    )


def overlap(strs):

    return reduce(
        lambda s1, s2:
            s1 + s2[max_overlap(s1, s2):],
        strs, '',
    )


overlap(l)
#> 'volcanowayleasequencerupt'

然而，它还考虑了之前重叠单词中“累积”的字符:

overlap(['split', 'it', 'lit'])
#> 'split'

- EliadL

---

值得一提的是，这里使用了 __add__，它速度较慢，每个列表项最多需要进行 n 次重新分配和复制。这是 O(n^2) 的。稍微快一点的是 __iadd__。在 CPython 上，由于预分配保证了 O(n) 的性能（以及其他一些原因），str.join 比它们都要快。 - Mateen Ulhaq

@MateenUlhaq 感谢您的见解。确实，我是根据 OP 的要求去寻找“最 Pythonic”的方法，而不是“最有效”的方法： “我正在寻找最 Pythonic 的方法。” - EliadL

Answer 3

Here's a brute-force deduplicator:

def dedup(a, b):
    for i in range(len(b), 0, -1):
        if a[-i:] == b[:i]:
            return a[:-i]
    return a

然后，简单快速地完成以下步骤：

>>> from itertools import chain, islice
>>> xs = ["volcano", "noway", "lease", "sequence", "erupt"]
>>> xs = [dedup(*x) for x in zip(xs, chain(islice(xs, 1, None), [""]))]
>>> "".join(xs)
'volcanowayleasequencerupt'

自然，这适用于任何长度的列表xs。

- Mateen Ulhaq