Python的字符串组合成尽可能短的字符串？ [英] Python Combining strings into the shortest possible string?

问题描述

如果我有一个字符串列表，我想将它们组合成一个字符串重叠的字符。如果没有留下只是没有重叠的字符串它添加到末尾。这是一个过于简化版本。

If I have a list of strings, I would like to combine them into one string with overlapping characters. If there is no overlapping strings left just add it to the end. Here is an overly simplified version.

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

我正在寻找一些方法来做到这一点与任意数量的输入字符串列表。

What i'm looking for as some way to do that with any number of strings in the input list.

谢谢，
giodamelio

Thanks,
giodamelio

推荐答案

这是不是真的不够好举一个简单的例子。这只是关于（农历）一年中最得以确认的问题。但是假设重叠只能发生在两端，并且每个单词测试只有两次（对电流输出的每一端），并且希望最大程度的重叠，这将做的工作：

It isn't really good enough to give one trivial example. This is just about the most underspecified question of the (lunar) year. However assuming that overlap can occur only the ends, and each word is tested only twice (against each end of the current output), and you want the maximum overlap, this would do the job:

[bug修正后编辑] 的

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'

这篇关于Python的字符串组合成尽可能短的字符串？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！