Problem:A string is k pallindrome if it can be transformed into a palindrome on removing at most k characters from it.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 |
/*You are required to complete this function*/ bool is_k_pallin(string s,int k) { //Your code here string rev_s=""; int n = s.size(); for(int i=s.size()-1;i>=0;i--) rev_s.append(1u,s[i]); int dp[n+1][n+1]; for(int i=0;i<=n;i++) { for(int j=0;j<=n;j++) { if(i==0) dp[i][j]=j; else if(j==0) dp[i][j]=i; else if(s[i-1]==rev_s[j-1]) dp[i][j]=dp[i-1][j-1]; else if(s[i-1]!=rev_s[j-1]) dp[i][j] = 1+ (dp[i-1][j]<dp[i][j-1]?dp[i-1][j]:dp[i][j-1]); } } if(dp[n][n]<=2*k) return 1; return 0; } |