Сегодняшний вопрос - это дополнительная функция к вопросу о суперпоследовательности, который мы решили вчера. Если вы хотите узнать о нем больше, вы можете перейти по этой ссылке.
1092. Кратчайшая общая суперпоследовательность
Учитывая две строки str1 и str2, верните самую короткую строку, которая содержит как str1, так и str2 в качестве подпоследовательностей. Если существует несколько ответов, вы можете вернуть любой из них.
(Строка S является подпоследовательностью строки T, если удаление некоторого количества символов из T (возможно, 0, и символы выбираются где-нибудь из T) приводит к строке S.)
Пример 1:
Input: str1 = "abac", str2 = "cab" Output: "cabac" Explanation: str1 = "abac" is a subsequence of "cabac" because we can delete the first "c". str2 = "cab" is a subsequence of "cabac" because we can delete the last "ac". The answer provided is the shortest such string that satisfies these properties.
Примечание.
1 <= str1.length, str2.length <= 1000str1иstr2состоят из строчных букв английского алфавита.
Прежде чем перейти к решению, давайте вспомним значение суперпоследовательности.
Согласно Википедии,
В информатике кратчайшая общая суперпоследовательность двух последовательностей X и Y - это кратчайшая последовательность, имеющая X и Y как подпоследовательности. Кратчайшая общая суперпоследовательность (SCS) - это обычная суперпоследовательность минимальной длины. В задаче о кратчайшей общей суперпоследовательности даны две последовательности X и Y, и задача состоит в том, чтобы найти кратчайшую возможную общую суперпоследовательность этих последовательностей. В общем, СКС не уникальна.
Напомним и код решения СКС.
class FindShortest:
def shortestCommonSupersequence(self, text1: str, text2: str) -> int:
memo = [[0 for j in range(len(text2)+1)]for i in range(len(text1)+1)]
for i in range(1, len(memo)):
for j in range(1, len(memo[0])):
if text1[i-1] == text2[j-1]:
memo[i][j] = 1 + memo[i-1][j-1]
else:
memo[i][j] = max(memo[i-1][j], memo[i][j-1])
return len(text1)+ len(text2) + memo[-1][-1]
Мы научились печатать самую длинную общую подпоследовательность в предыдущих публикациях. Чтобы напечатать кратчайшую общую суперпоследовательность, мы будем использовать аналогичную стратегию.
Одно из основных различий между LCS и SCS заключается в том, что в SCS мы включаем необычные символы, а также символы LCS. Поскольку нам нужна только кратчайшая общая суперпоследовательность, мы будем включать символы LCS один раз.
Хорошо, имея это в виду, давайте продолжим поиск решения.
Давайте возьмем пример и решим его.
Пусть входными строками будут «AGGTAB» и «GXTXAYB». Когда мы запускаем приведенный выше код для данной входной строки, давайте увидим содержимое в матрице.
Давайте инициализируем переменную «answer», в которой будет храниться результат.
Когда мы пытались распечатать LCS, мы начали с последней ячейки в матрице мемоизации. Аналогично, чтобы распечатать SCS, мы начнем с последней ячейки.
Мы проверим, равен ли символ i-1-го индекса строки 1 символу j-1-го индекса строки 2. Если да, мы добавляем его в переменную ответа. Если символы не совпадают, в LCS мы ищем максимум между ячейкой до верха текущей ячейки и слева от текущей ячейки, а затем продвигаемся вперед. Точно так же мы поступим и в SCS, но здесь мы добавим символ в переменную ответа. Это означает, что если мы переместимся влево от текущей ячейки, мы добавим j-1-й символ из строки 2. В противном случае мы добавим i-1-й символ из строки1.
Прежде чем мы рассмотрим код для печати SCS, давайте вспомним код для печати LCS.
class FindLongest:
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
memo = [[float('-inf') for j in range(len(text2)+1)]for i in range(len(text1)+1)]
for i in range(len(memo)):
for j in range(len(memo[0])):
if i == 0 or j == 0:
memo[i][j] = 0
elif text1[i-1] == text2[j-1]:
memo[i][j] = 1 + memo[i-1][j-1]
else:
memo[i][j] = max(memo[i-1][j], memo[i][j-1])
i = len(memo)-1
j = len(memo[0])-1
ans = ""
while(i >= 0 and j >= 0):
if text1[i-1] == text2[j-1]:
ans += text1[i-1]
i -= 1
j -= 1
else:
if memo[i-1][j] > memo[i][j-1]:
i -= 1
else:
j -= 1
return(ans[::-1])
Один из крайних случаев, о котором следует помнить. Если одна из наших строк пуста, другой строкой будет SCS. Эту же логику нужно добавить и в наш алгоритм. Следующий фрагмент кода позаботится об этом.
while(i > 0):
ans += str1[i-1]
i -= 1
while(j > 0):
ans += str2[j-1]
j -= 1
Давайте рассмотрим полный фрагмент кода.
class PrintShortestCommonSupersequence:
def shortestCommonSupersequence(self, str1: str, str2: str) -> str:
memo = [[0 for j in range(len(str2)+1)]for i in range(len(str1)+1)]
for i in range(1, len(memo)):
for j in range(1, len(memo[0])):
if str1[i-1] == str2[j-1]:
memo[i][j] = memo[i-1][j-1] + 1
else:
memo[i][j] = max(memo[i-1][j], memo[i][j-1])
ans = ""
i = len(memo)-1
j = len(memo[0])-1
while(i > 0 and j > 0):
if str1[i-1] == str2[j-1]:
ans += str1[i-1]
i -= 1
j -= 1
else:
if memo[i-1][j] > memo[i][j-1]:
ans += str1[i-1]
i -= 1
else:
ans += str2[j-1]
j -= 1
while(i > 0):
ans += str1[i-1]
i -= 1
while(j > 0):
ans += str2[j-1]
j -= 1
return ans[::-1]
Анализ сложности.
Сложность времени
Мы проходим через двумерный массив размера M * N, следовательно, временная сложность равна O (M * N), где M - размер строки1, а N - размер строки2.
Космическая сложность.
Мы создаем 2D-массив размером M * N, следовательно, сложность пространства равна O (M * N), где M - размер строки1, а N - размер строки2.
Ссылка на видео Адитьи Вермы
