Python将字符串组合成最短的字符串？

Question

如果我有一个字符串列表,我想将它们组合成一个重叠字符的字符串.如果没有重叠的字符串,只需将其添加到结尾.这是一个过于简化的版本.

input = ['one', 'two']
output = 'twone'

我在寻找输入列表中任意数量的字符串的一些方法.

谢谢,
giodamelio

Answer 1

给出一个简单的例子并不是很好.这是关于(农历)年最不明确的问题.然而,假设重叠只能在结束时发生,并且每个单词仅测试两次(对于当前输出的每一端),并且您想要最大重叠,这将完成工作:

[编辑后修正错误]

def glue(a, b):
    maxn = 0
    for n in xrange(1, 1 + min(len(a), len(b))):
        suffix = a[-n:]
        prefix = b[:n]
        if prefix == suffix:
            maxn = n
    # BUG: return maxn, a[:-maxn] + b
    # FAILS when maxn == 0
    # EXTRA TEST: ['nil', 'overlap']
    return a + b[maxn:]     


def multiglue(words):
    if not words: return ""
    result = words[0]
    for word in words[1:]:
        nx, rx = glue(result, word)
        ny, ry = glue(word, result)
        result = rx if nx > ny else ry
    return result

tests = [line.split() for line in """
    one
    two one
    one two
    overlap nil
    nil overlap
    toad dog rabbit
    frog ogham
    ogham frog
    hopper grasshopper
    grass grasshopper person
    foooo oooof
    oooof foooo""".splitlines()]

for test in tests:
    out = multiglue(test)
    print test, repr(out)

输出:

[] ''
['one'] 'one'
['two', 'one'] 'twone'
['one', 'two'] 'twone'
['overlap', 'nil'] 'niloverlap'
['nil', 'overlap'] 'overlapnil'
['toad', 'dog', 'rabbit'] 'rabbitoadog'
['frog', 'ogham'] 'frogham'
['ogham', 'frog'] 'frogham'
['hopper', 'grasshopper'] 'grasshopper'
['grass', 'grasshopper', 'person'] 'grasshopperson'
['foooo', 'oooof'] 'foooof'
['oooof', 'foooo'] 'foooof'