python - 如果字符串有重叠区域，则连接它们

Question

我正在尝试编写一个脚本，该脚本将查找在每个字符串的开头或结尾处共享 5 个字母的重叠区域的字符串（如下面的示例所示）。

facgakfjeakfjekfzpgghi
                 pgghiaewkfjaekfjkjakjfkj
                                    kjfkjaejfaefkajewf

我正在尝试创建一个连接所有三个的新字符串，因此输出将是：

facgakfjeakfjekfzpgghiaewkfjaekfjkjakjfkjaejfaefkajewf

编辑：

这是输入：

x = ('facgakfjeakfjekfzpgghi', 'kjfkjaejfaefkajewf', 'pgghiaewkfjaekfjkjakjfkj')

**列表未排序

到目前为止我写的 * 但不正确：

def findOverlap(seq)
    i = 0
    while i < len(seq): 
        for x[i]:
        #check if x[0:5] == [:5] elsewhere

 x = ('facgakfjeakfjekfzpgghi', 'kjfkjaejfaefkajewf', 'pgghiaewkfjaekfjkjakjfkj')
findOverlap(x)

Answer 1

创建一个字典，将每个字符串的前 5 个字符映射到它的尾部

strings = {s[:5]: s[5:] for s in x}

和一组所有的后缀：

suffixes = set(s[-5:] for s in x)

现在找到前缀不匹配任何后缀的字符串：

prefix = next(p for p in strings if p not in suffixes)

现在我们可以遵循字符串链：

result = [prefix]
while prefix in strings:
    result.append(strings[prefix])
    prefix = strings[prefix][-5:]
print "".join(result)

Answer 2

蛮力方法 - 执行所有组合并返回匹配链接项的第一个：

def solution(x):
    from itertools import permutations
    for perm in permutations(x):
        linked = [perm[i][:-5] for i in range(len(perm)-1) 
                               if perm[i][-5:]==perm[i+1][:5]]
        if len(perm)-1==len(linked):
            return "".join(linked)+perm[-1]
    return None

x = ('facgakfjeakfjekfzpgghi', 'kjfkjaejfaefkajewf', 'pgghiaewkfjaekfjkjakjfkj')
print solution(x)

Answer 3

循环遍历每对候选对象，反转第二个字符串并使用此处的答案