Сложность: hard
Дана строка s. За один шаг вы можете вставить любой символ в любой индекс строки.
Верните минимальное количество шагов, необходимых для превращения s в палиндром.
Палиндром — это строка, которая читается одинаково как вперед, так и назад.
Пример:
Input: s = "zzazz"
Output: 0
Explanation: The string "zzazz" is already palindrome we do not need any insertions.
👨💻 Алгоритм:
1⃣Создайте целочисленную переменную n и инициализируйте её размером строки s. Создайте строковую переменную sReverse и установите её значение как обратную строку s.
2⃣Создайте двумерный массив memo размером n + 1 на n + 1, где memo[i][j] будет содержать длину наибольшей общей подпоследовательности, учитывая первые i символов строки s и первые j символов строки sReverse. Инициализируйте массив значением -1.
3⃣Верните n - lcs(s, sReverse, n, n, memo), где lcs - это рекурсивный метод с четырьмя параметрами: первая строка s1, вторая строка s2, длина подстроки от начала s1, длина подстроки от начала s2 и memo. Метод возвращает длину наибольшей общей подпоследовательности в подстроках s1 и s2. В этом методе выполните следующее:
Если m == 0 или n == 0, это означает, что одна из двух подстрок пуста, поэтому верните 0.
Если memo[m][n] != -1, это означает, что мы уже решили эту подзадачу, поэтому верните memo[m][n].
Если последние символы подстрок совпадают, добавьте 1 и найдите длину наибольшей общей подпоследовательности, исключив последний символ обеих подстрок. Верните memo[i][j] = 1 + lcs(s1, s2, m - 1, n - 1, memo).
В противном случае, если последние символы не совпадают, рекурсивно найдите наибольшую общую подпоследовательность в обеих подстроках, исключив их последние символы по одному. Верните memo[i][j] = max(lcs(s1, s2, m - 1, n, memo), lcs(s1, s2, m, n - 1, memo)).
😎 Решение:
class Solution:
def lcs(self, s1, s2, m, n, memo):
if m == 0 or n == 0:
return 0
if memo[m][n] != -1:
return memo[m][n]
if s1[m - 1] == s2[n - 1]:
memo[m][n] = 1 + self.lcs(s1, s2, m - 1, n - 1, memo)
else:
memo[m][n] = max(self.lcs(s1, s2, m - 1, n, memo), self.lcs(s1, s2, m, n - 1, memo))
return memo[m][n]
def minInsertions(self, s: str) -> int:
n = len(s)
sReverse = s[::-1]
memo = [[-1] * (n + 1) for _ in range(n + 1)]
return n - self.lcs(s, sReverse, n, n, memo)
Ставь 👍 и забирай 📚 Базу знаний