Как сравнить множество строк и подобрать верную последовательность?

Question

На вход приходит n и n-ое кол-во строк. Строки состоят из последовательностей букв английского алфавита. Задача подобрать такую последовательность, чтобы начало каждой строки совпадало с концом(по 3 символа брать для проверки) другой. Ответ должен выводиться в строке, которая отображает в какой последовательности вывести начальную последовательность строк.

Как такое реализовать?

Сам додумался только как принимать эти строки:

n = int(input())
spis = []
for i in range(0,n):
    c = input()
    spis.append(c)

Но дальше не могу сдвинуться. Идей совсем нет(

Написать надо стандартными средствами Python

Вот таким образом получил список совмещаемых и нет:

a = int(input())
spis = []
res = ""
good = {}
bad = {}
for i in range(0,a):
    c = input()
    spis.append(c)
for i in spis:
    for c in range(0,len(spis)):
        if (i[:3] == spis[c][-3:]) and (i!=spis[c]):
            good.update({spis[c]:i})
        else:
            bad.update({spis[c]:i})

Как теперь отсюда вывести подходящее и сформировать нужную строку?

Answer 1

Всё я напутал, не так надо...

Нужно построить ориентированный граф, где узлы - трёхсимвольные концы и начала, а дуги - исходные строки. Если строка кончается на 'abc', она является входящим ребром (дугой) для 'abc', а если начинается - то исходящим.

Потом для полученного графа найти эйлеров путь e-maxx, itmo

старый ответ пока оставлю

Проверить для каждой строки, с началом каких совпадает её конец, и построить орграф, где узлы - строки, а дуги - совпадения.

Граф может выглядеть как список смежности (список списков A[][]_, для i-й строки A[i] содержит список номеров строк, с которыми совместим конец spis[i]

a = int(input())
spis = []
for i in range(a):
    spis.append(input())

A =[[] for _ in range(len(spis))]
for i in range(len(spis)):
    for c in range(len(spis)):
        if (spis[i][:3] == spis[c][-3:]) and (i!=c):
             A[c].append(i)
print(A)


4
123456
456789
456999
999123

[[1, 2], [], [3], [0]]

Затем найти эйлеров путь для данного графа. Описаний алгоритма в сети немало, на Python можно воспользоватьcя networkx.eulerian_path

БЛОГ НА HUSL

Как сравнить множество строк и подобрать верную последовательность?

Ответы (1 шт):