Palindrome Partitioning | DP | Using memoizatoin to solve the partition problem . ; Function to check if input string is pallindrome or not ; Using two pointer technique to check pallindrome ; Function to find keys for the Hashmap ; Returns the minimum number of cuts needed to partition a string such that every part is a palindrome ; Key for the Input String ; If the no of partitions for string " ij " is already calculated then return the calculated value using the Hashmap ; Every String of length 1 is a pallindrome ; Make a cut at every possible location starting from i to j ; If left cut is found already ; If right cut is found already ; Recursively calculating for left and right strings ; Taking minimum of all k possible cuts ; Return the min cut value for complete string . ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; bool ispallindrome ( string input , int start , int end ) { while ( start < end ) { if ( input [ start ] != input [ end ] ) return false ; start ++ ; end -- ; } return true ; } string convert ( int a , int b ) { return to_string ( a ) + " " + to_string ( b ) ; } int minpalparti_memo ( string input , int i , int j , unordered_map < string , int > & memo ) { if ( i > j ) return 0 ; string ij = convert ( i , j ) ; if ( memo . find ( ij ) != memo . end ( ) ) { return memo [ ij ] ; } if ( i == j ) { memo [ ij ] = 0 ; return 0 ; } if ( ispallindrome ( input , i , j ) ) { memo [ ij ] = 0 ; return 0 ; } int minimum = INT_MAX ; for ( int k = i ; k < j ; k ++ ) { int left_min = INT_MAX ; int right_min = INT_MAX ; string left = convert ( i , k ) ; string right = convert ( k + 1 , j ) ; if ( memo . find ( left ) != memo . end ( ) ) { left_min = memo [ left ] ; } if ( memo . find ( right ) != memo . end ( ) ) { right_min = memo [ right ] ; } if ( left_min == INT_MAX ) left_min = minpalparti_memo ( input , i , k , memo ) ; if ( right_min == INT_MAX ) right_min = minpalparti_memo ( input , k + 1 , j , memo ) ; minimum = min ( minimum , left_min + 1 + right_min ) ; } memo [ ij ] = minimum ; return memo [ ij ] ; } int main ( ) { string input = " ababbbabbababa " ; unordered_map < string , int > memo ; cout << minpalparti_memo ( input , 0 , input . length ( ) - 1 , memo ) << endl ; return 0 ; }