Возвращение объединенную строку

def word_mesh(words: [str]) -> str:
    result = ""
    for current, follow in zip(words, words[1:]):
        for i in range(max(len(current), len(follow))):
            if follow.startswith(current[i:]):
                result += current[i:]
                break
    return "failed" if not result else result

from collections import defaultdict
from copy import copy
 
 
def find_path(start: str, graph: list, selected: list = None) -> list:
    selected = (selected or []) + [start]
    if len(selected) == len(graph):
        return selected
    for vertex in graph[start]:
        ans = find_path(vertex, graph, copy(selected))
        if ans is not None:
            return ans
    return None
 
 
def build_join(path: list) -> str:
    ans = []
    for left, right in zip(path, path[1:]):
        for i in range(1, min(len(left), len(right))):
            suffix = left[-i:]
            if right.startswith(suffix):
                ans.append(suffix)
                break
    return ''.join(ans)
 
 
def word_mesh(words: list) -> str:
    graph: dict = defaultdict(set)
    for word in words:
        for start in range(1, len(word)):
            for match in filter(lambda match: match.startswith(word[start:]) \
                                              and match != word, words):
                graph[word].add(match)
    for start in graph.keys():
        path = find_path(start, graph)
        if path is not None:
            return build_join(path)
    return "failed"
 
 
ans = word_mesh(["allow", "lowering", "ringmaster", "terror"])
print(ans)

def prefix_function(s):
    n = len(s)
    p = [0] * n
    for i in range(1, n):
        k = p[i - 1]
        while k > 0 and s[i] != s[k]:
            k = p[k - 1]
        if s[i] == s[k]:
            k += 1
        p[i] = k
    return p
 
 
def word_mesh(arr):
    res = ''
    for a, b in zip(arr, arr[1:]):
        res += b[:prefix_function(b+'#'+a)[-1]]
    return res
 
 
print(word_mesh(["allow", "lowering", "ringmaster", "terror"]))