Восстановление исходной строки из частичных строк с отсутствующими буквами ⇐ Python

[Anonymous]

У меня есть строка длины n, скажем «ABCDEFG». Строка может содержать повторяющиеся символы, поэтому "ABCBCAGFH" также является допустимой строкой.
У меня также есть список строк, которые созданы из исходной строки, но отсутствуют одна или несколько букв, например ["BCDEFG", "ADEFG", "ABC"]. Список может иметь дубликаты и имеет длину m. Буквы в списке всегда будут идти в том же порядке, что и в исходной строке, например. буква "D" всегда будет перед "EFG" и после "ABC".
Мне нужно восстановить исходную строку, используя только строки в списке.
Я дошел до того, что могу извлечь все подстроки, но у меня возникли проблемы с размещением этих подстрок в нужном месте, как это видно в примере ниже. .
Вот мой код на Python:

Код: Выделить всё

def reconstruct_string(partial_strings):
"""Reconstructs the original string from a list of partial strings.

Args:
partial_strings: A list of partial strings.

Returns:
The reconstructed original string, or None if it cannot be restored.
"""

missing_letters = []
temp_substring = ""
result = ""

for string_1 in partial_strings:
for string_2 in partial_strings[partial_strings.index(string_1) + 1 : ]:
for i in range(len(string_1)):
for j in range(len(string_2)):
if string_1[i] == string_2[j]:
temp_substring += string_1[i]

if string_1[i] in missing_letters:
missing_letters.remove(string_1[i])
break

elif string_1[i] not in string_2 and string_1[i] not in missing_letters \
and string_1[i] not in temp_substring:
missing_letters.append(string_1[i])

elif string_2[j] not in string_1 and string_2[j] not in missing_letters \
and string_2[j] not in temp_substring:
missing_letters.append(string_2[j])

result += temp_substring
print(f"{missing_letters=}\n{temp_substring=}\n{result=}\n")
temp_substring = ""

# Example usage
temp_solutions = ["ABC", "BCDEFG", "ADEFG"]
result = reconstruct_string(temp_solutions)

Инструкция печати возвращает:

Код: Выделить всё

missing_letters=['A', 'D', 'E', 'F', 'G']
temp_substring='BC'
result='BC'

missing_letters=['D', 'E', 'F', 'G', 'B', 'C']
temp_substring='A'
result='BCA'

missing_letters=['B', 'C', 'A']
temp_substring='DEFG'
result='BCADEFG'

Эти частичные строки получены из показаний OCR, которые могут быть неполными, поэтому список частичных строк представляет собой показания, сделанные под разными углами, в надежде на возможность восстановить полную строку.
>

Подробнее здесь: https://stackoverflow.com/questions/790 ... ng-letters