Сложность: hard
Дана строка s и целое число k. Верните true, если s является k-палиндромом.
Строка является k-палиндромом, если её можно преобразовать в палиндром, удалив из неё не более k символов.
Пример:
Input: s = "abcdeca", k = 2
Output: true
Explanation: Remove 'b' and 'e' characters.
👨💻 Алгоритм:
1⃣Инициализируйте двухмерный массив memo для хранения промежуточных результатов, чтобы избежать повторных вычислений. Определите функцию isValidPalindrome, которая будет возвращать минимальное количество удалений для создания палиндрома в подстроке от индекса i до j.
2⃣Реализуйте базовые случаи для функции isValidPalindrome: если i равно j, то это уже палиндром, если i и j - соседние индексы, то возвращается 1, если символы не совпадают. Если значение для пары индексов уже рассчитано, то возвращается сохраненное значение из memo.
3⃣Реализуйте основные случаи рекурсивного вычисления: если символы на позициях i и j совпадают, продолжайте проверку для подстроки без этих символов. В противном случае, рассмотрите два варианта удаления символов и выберите минимальное количество удалений, добавив 1 за текущее удаление.
😎 Решение:
class Solution:
def isValidPalindrome(self, s: str, k: int) -> bool:
n = len(s)
memo = [[None] * n for _ in range(n)]
def isValidPalindromeHelper(i, j):
if i == j:
return 0
if i == j - 1:
return 1 if s[i] != s[j] else 0
if memo[i][j] is not None:
return memo[i][j]
if s[i] == s[j]:
memo[i][j] = isValidPalindromeHelper(i + 1, j - 1)
else:
memo[i][j] = 1 + min(isValidPalindromeHelper(i + 1, j), isValidPalindromeHelper(i, j - 1))
return memo[i][j]
return isValidPalindromeHelper(0, n - 1) <= k
Ставь 👍 и забирай 📚 Базу знаний