Minimum number of deletions to make a string palindrome | Set 2 | Python3 program to find minimum deletions to make palindrome . ; Find reverse of input string ; Create a DP table for storing edit distance of string and reverse . ; Find edit distance between input and revInput considering only delete operation . ; Go from bottom left to top right and find the minimum ; Driver Code
INT_MAX = 99999999999 NEW_LINE def getLevenstein ( inpt ) : NEW_LINE INDENT revInput = inpt [ : : - 1 ] NEW_LINE n = len ( inpt ) NEW_LINE dp = [ [ - 1 for _ in range ( n + 1 ) ] for __ in range ( n + 1 ) ] NEW_LINE for i in range ( n + 1 ) : NEW_LINE INDENT dp [ 0 ] [ i ] = i NEW_LINE dp [ i ] [ 0 ] = i NEW_LINE DEDENT for i in range ( 1 , n + 1 ) : NEW_LINE INDENT for j in range ( 1 , n + 1 ) : NEW_LINE INDENT if inpt [ i - 1 ] == revInput [ j - 1 ] : NEW_LINE INDENT dp [ i ] [ j ] = dp [ i - 1 ] [ j - 1 ] NEW_LINE DEDENT else : NEW_LINE INDENT dp [ i ] [ j ] = 1 + min ( dp [ i - 1 ] [ j ] , dp [ i ] [ j - 1 ] ) NEW_LINE DEDENT DEDENT DEDENT res = INT_MAX NEW_LINE i , j = n , 0 NEW_LINE while i >= 0 : NEW_LINE INDENT res = min ( res , dp [ i ] [ j ] ) NEW_LINE if i < n : NEW_LINE INDENT res = min ( res , dp [ i + 1 ] [ j ] ) NEW_LINE DEDENT if i > 0 : NEW_LINE INDENT res = min ( res , dp [ i - 1 ] [ j ] ) NEW_LINE DEDENT i -= 1 NEW_LINE j += 1 NEW_LINE DEDENT return res NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT inpt = " myfirstgeekarticle " NEW_LINE print ( getLevenstein ( inpt ) ) NEW_LINE DEDENT