Untitled

 avatar
unknown
plain_text
6 months ago
1.0 kB
2
Indexable
//12458 - Writing APP
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#define max 1002

int memo[max][max][22];

bool can_palindrome(char*s, int left, int right, int k)
{
    if(k < 0)
        return false;//important
    
    if(left >= right)//don't forget '='
        return true;

    if(memo[left][right][k] != -1)
        return memo[left][right][k];

    if(s[left] == s[right])
        memo[left][right][k] = can_palindrome(s, left+1, right-1, k);
    else
        memo[left][right][k] = can_palindrome(s, left+1, right, k-1) ||
                               can_palindrome(s, left, right-1, k-1);//k remember to -1
                               
    return memo[left][right][k];
}
int main(void)
{
    int n, k;
    char str[max];

    memset(memo, -1, sizeof(memo));

    scanf("%d %d", &n, &k);
    scanf("%s", &str);

    if(can_palindrome(str, 0, n-1, k))
        printf("Yes\n");
    else
        printf("No\n");

    return 0;
}
Editor is loading...
Leave a Comment