Задача: 1216. Valid Palindrome III
Сложность: 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 за текущее удаление.

😎 Решение:

public class Solution {
    private int[,] memo;

    private int IsValidPalindromeHelper(char[] s, int i, int j) {
        if (i == j) return 0;
        if (i == j - 1) return s[i] != s[j] ? 1 : 0;
        if (memo[i, j] != -1) return memo[i, j];
        if (s[i] == s[j]) {
            memo[i, j] = IsValidPalindromeHelper(s, i + 1, j - 1);
        } else {
            memo[i, j] = 1 + Math.Min(IsValidPalindromeHelper(s, i + 1, j), IsValidPalindromeHelper(s, i, j - 1));
        }
        return memo[i, j];
    }

    public bool IsValidPalindrome(string s, int k) {
        int n = s.Length;
        memo = new int[n, n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                memo[i, j] = -1;
            }
        }
        return IsValidPalindromeHelper(s.ToCharArray(), 0, n - 1) <= k;
    }
}

Ставь 👍 и забирай 📚 Базу знаний