Minimum insertions to form a palindrome | DP | A utility function to find minimum of two integers ; A DP function to find minimum number of insertions ; Create a table of size n * n . table [ i ] [ j ] will store minimum number of insertions needed to convert str1 [ i . . j ] to a palindrome . ; Fill the table ; Return minimum number of insertions for str1 [ 0. . n - 1 ] ; Driver Code
def Min ( a , b ) : NEW_LINE INDENT return min ( a , b ) NEW_LINE DEDENT def findMinInsertionsDP ( str1 , n ) : NEW_LINE INDENT table = [ [ 0 for i in range ( n ) ] for i in range ( n ) ] NEW_LINE l , h , gap = 0 , 0 , 0 NEW_LINE for gap in range ( 1 , n ) : NEW_LINE INDENT l = 0 NEW_LINE for h in range ( gap , n ) : NEW_LINE INDENT if str1 [ l ] == str1 [ h ] : NEW_LINE INDENT table [ l ] [ h ] = table [ l + 1 ] [ h - 1 ] NEW_LINE DEDENT else : NEW_LINE INDENT table [ l ] [ h ] = ( Min ( table [ l ] [ h - 1 ] , table [ l + 1 ] [ h ] ) + 1 ) NEW_LINE DEDENT l += 1 NEW_LINE DEDENT DEDENT return table [ 0 ] [ n - 1 ] ; NEW_LINE DEDENT str1 = " geeks " NEW_LINE print ( findMinInsertionsDP ( str1 , len ( str1 ) ) ) NEW_LINE