Сложность: hard
Учитывая массив строк words, верните наименьшую строку, которая содержит каждую строку в words в качестве подстроки. Если существует несколько допустимых строк наименьшей длины, верните любую из них. Вы можете предположить, что ни одна строка в words не является подстрокой другой строки в words.
Пример:
Input: words = ["alex","loves","leetcode"]
Output: "alexlovesleetcode"
👨💻 Алгоритм:
1⃣Реализовать функцию overlap для вычисления максимального перекрытия двух строк, где одна строка заканчивается, а другая начинается.
2⃣Реализовать функцию merge для объединения двух строк с максимальным перекрытием.
Использовать жадный алгоритм для нахождения двух строк с максимальным перекрытием и объединить их, повторяя до тех пор, пока не останется одна строка.
3⃣Вернуть результат.
😎 Решение:
def shortestSuperstring(words):
def overlap(a, b):
max_overlap = 0
for i in range(1, min(len(a), len(b)) + 1):
if a[-i:] == b[:i]:
max_overlap = i
return max_overlap
def merge(a, b, overlap_len):
return a + b[overlap_len:]
while len(words) > 1:
max_overlap = -1
l, r = 0, 0
for i in range(len(words)):
for j in range(len(words)):
if i != j:
ovlp = overlap(words[i], words[j])
if ovlp > max_overlap:
max_overlap = ovlp
l, r = i, j
words.append(merge(words[l], words[r], max_overlap))
words.pop(r)
words.pop(l)
return words[0]
Ставь 👍 и забирай 📚 Базу знаний