Palindrome Partitioning | DP | Returns the minimum number of cuts needed to partition a string such that every part is a palindrome ; Get the length of the string ; Create two arrays to build the solution in bottom up manner C [ i ] [ j ] = Minimum number of cuts needed for palindrome partitioning of substring str [ i . . j ] P [ i ] [ j ] = true if substring str [ i . . j ] is palindrome , else false . Note that C [ i ] [ j ] is 0 if P [ i ] [ j ] is true ; different looping variables ; Every substring of length 1 is a palindrome ; L is substring length . Build the solution in bottom - up manner by considering all substrings of length starting from 2 to n . The loop structure is the same as Matrix Chain Multiplication problem ( See https : www . geeksforgeeks . org / matrix - chain - multiplication - dp - 8 / ) ; For substring of length L , set different possible starting indexes ; Set ending index ; If L is 2 , then we just need to compare two characters . Else need to check two corner characters and value of P [ i + 1 ] [ j - 1 ] ; IF str [ i . . j ] is palindrome , then C [ i ] [ j ] is 0 ; Make a cut at every possible location starting from i to j , and get the minimum cost cut . ; Return the min cut value for complete string . i . e . , str [ 0. . n - 1 ] ; Driver code
def minPalPartion ( str ) : NEW_LINE INDENT n = len ( str ) NEW_LINE C = [ [ 0 for i in range ( n ) ] for i in range ( n ) ] NEW_LINE P = [ [ False for i in range ( n ) ] for i in range ( n ) ] NEW_LINE j = 0 NEW_LINE k = 0 NEW_LINE L = 0 NEW_LINE for i in range ( n ) : NEW_LINE INDENT P [ i ] [ i ] = True ; NEW_LINE C [ i ] [ i ] = 0 ; NEW_LINE DEDENT for L in range ( 2 , n + 1 ) : NEW_LINE INDENT for i in range ( n - L + 1 ) : NEW_LINE INDENT j = i + L - 1 NEW_LINE if L == 2 : NEW_LINE INDENT P [ i ] [ j ] = ( str [ i ] == str [ j ] ) NEW_LINE DEDENT else : NEW_LINE INDENT P [ i ] [ j ] = ( ( str [ i ] == str [ j ] ) and P [ i + 1 ] [ j - 1 ] ) NEW_LINE DEDENT if P [ i ] [ j ] == True : NEW_LINE INDENT C [ i ] [ j ] = 0 NEW_LINE DEDENT else : NEW_LINE INDENT C [ i ] [ j ] = 100000000 NEW_LINE for k in range ( i , j ) : NEW_LINE INDENT C [ i ] [ j ] = min ( C [ i ] [ j ] , C [ i ] [ k ] + C [ k + 1 ] [ j ] + 1 ) NEW_LINE DEDENT DEDENT DEDENT DEDENT return C [ 0 ] [ n - 1 ] NEW_LINE DEDENT str = " ababbbabbababa " NEW_LINE print ( ' Min ▁ cuts ▁ needed ▁ for ▁ Palindrome ▁ Partitioning ▁ is ' , minPalPartion ( str ) ) NEW_LINE