1216. Valid Palindrome III

leetcode hard

#array#csharp#dynamic-programming#hard#leetcode#math#recursion#string

Task

Дана строка s и целое число k. Верните true, если s является k-палиндромом.

Строка является k-палиндромом, если её можно преобразовать в палиндром, удалив из неё не более k символов.

Пример:

Input: s = "abcdeca", k = 2

Output: true

Explanation: Remove 'b' and 'e' characters.

C# solution

matched/original

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;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    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 + 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.size();
        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;
    }
}

Java solution

matched/original

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;
    }
};

Python solution

matched/original

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

Explanation

Algorithm

1⃣Инициализируйте двухмерный массив memo для хранения промежуточных результатов, чтобы избежать повторных вычислений. Определите функцию isValidPalindrome, которая будет возвращать минимальное количество удалений для создания палиндрома в подстроке от индекса i до j.

2⃣Реализуйте базовые случаи для функции isValidPalindrome: если i равно j, то это уже палиндром, если i и j - соседние индексы, то возвращается 1, если символы не совпадают. Если значение для пары индексов уже рассчитано, то возвращается сохраненное значение из memo.

3⃣Реализуйте основные случаи рекурсивного вычисления: если символы на позициях i и j совпадают, продолжайте проверку для подстроки без этих символов. В противном случае, рассмотрите два варианта удаления символов и выберите минимальное количество удалений, добавив 1 за текущее удаление.

😎