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
def ispallindrome ( input , start , end ) : NEW_LINE INDENT while ( start < end ) : NEW_LINE INDENT if ( input [ start ] != input [ end ] ) : NEW_LINE INDENT return False ; NEW_LINE DEDENT start += 1 NEW_LINE end -= 1 NEW_LINE DEDENT return True ; NEW_LINE DEDENT def convert ( a , b ) : NEW_LINE INDENT return str ( a ) + str ( b ) ; NEW_LINE DEDENT def minpalparti_memo ( input , i , j , memo ) : NEW_LINE INDENT if ( i > j ) : NEW_LINE INDENT return 0 ; NEW_LINE DEDENT ij = convert ( i , j ) ; NEW_LINE if ( ij in memo ) : NEW_LINE INDENT return memo [ ij ] ; NEW_LINE DEDENT if ( i == j ) : NEW_LINE INDENT memo [ ij ] = 0 ; NEW_LINE return 0 ; NEW_LINE DEDENT if ( ispallindrome ( input , i , j ) ) : NEW_LINE INDENT memo [ ij ] = 0 ; NEW_LINE return 0 ; NEW_LINE DEDENT minimum = 1000000000 NEW_LINE for k in range ( i , j ) : NEW_LINE INDENT left_min = 1000000000 NEW_LINE right_min = 1000000000 NEW_LINE left = convert ( i , k ) ; NEW_LINE right = convert ( k + 1 , j ) ; NEW_LINE if ( left in memo ) : NEW_LINE INDENT left_min = memo [ left ] ; NEW_LINE DEDENT if ( right in memo ) : NEW_LINE INDENT right_min = memo [ right ] ; NEW_LINE DEDENT if ( left_min == 1000000000 ) : NEW_LINE INDENT left_min = minpalparti_memo ( input , i , k , memo ) ; NEW_LINE DEDENT if ( right_min == 1000000000 ) : NEW_LINE INDENT right_min = minpalparti_memo ( input , k + 1 , j , memo ) ; NEW_LINE DEDENT minimum = min ( minimum , left_min + 1 + right_min ) ; NEW_LINE DEDENT memo [ ij ] = minimum ; NEW_LINE return memo [ ij ] ; NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT input = " ababbbabbababa " ; NEW_LINE memo = dict ( ) NEW_LINE print ( minpalparti_memo ( input , 0 , len ( input ) - 1 , memo ) ) NEW_LINE DEDENT