如果我有一个字符串列表,我想将它们组合成一个字符串重叠的字符。如果没有留下只是没有重叠的字符串它添加到末尾。这是一个过于简化版本。
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'