Minimum number of deletions to make a string palindrome | Function definition ; Base cases ; Checking the ndesired condition ; If yes increment the count ; If no ; Return the value form the table ; Else store the max tranforamtion from the subsequence ; Return the dp [ - 1 ] [ - 1 ] ; Driver code ; Initialize the array with - 1
#include <bits/stdc++.h> NEW_LINE using namespace std ; int dp [ 2000 ] [ 2000 ] ; int transformation ( string s1 , string s2 , int i , int j ) { if ( i >= ( s1 . size ( ) ) || j >= ( s2 . size ( ) ) ) return 0 ; if ( s1 [ i ] == s2 [ j ] ) { dp [ i ] [ j ] = 1 + transformation ( s1 , s2 , i + 1 , j + 1 ) ; } if ( dp [ i ] [ j ] != -1 ) { return dp [ i ] [ j ] ; } else dp [ i ] [ j ] = max ( transformation ( s1 , s2 , i , j + i ) , transformation ( s1 , s2 , i + 1 , j ) ) ; return dp [ s1 . size ( ) - 1 ] [ s2 . size ( ) - 1 ] ; } int main ( ) { string s1 = " geeksforgeeks " ; string s2 = " geeks " ; int i = 0 ; int j = 0 ; memset ( dp , -1 , sizeof dp ) ; cout << " MINIMUM ▁ NUMBER ▁ OF ▁ DELETIONS : ▁ " << ( s1 . size ( ) ) - transformation ( s1 , s2 , 0 , 0 ) << endl ; cout << " MINIMUM ▁ NUMBER ▁ OF ▁ INSERTIONS : ▁ " << ( s2 . size ( ) ) - transformation ( s1 , s2 , 0 , 0 ) << endl ; cout << ( " LCS ▁ LENGTH : ▁ " ) << transformation ( s1 , s2 , 0 , 0 ) ; }