Сложность: 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 {
Integer memo[][];
int isValidPalindrome(String s, int i, int j) {
if (i == j)
return 0;
if (i == j - 1)
return s.charAt(i) != s.charAt(j) ? 1 : 0;
if (memo[i][j] != null)
return memo[i][j];
if (s.charAt(i) == s.charAt(j))
return memo[i][j] = isValidPalindrome(s, i + 1, j - 1);
return memo[i][j] = 1 + Math.min(isValidPalindrome(s, i + 1, j), isValidPalindrome(s, i, j - 1));
}
public boolean isValidPalindrome(String s, int k) {
memo = new Integer[s.length()][s.length()];
return isValidPalindrome(s, 0, s.length() - 1) <= k;
}
};Ставь 👍 и забирай 📚 Базу знаний