Minimum insertions to form a palindrome | DP | A Naive recursive program to find minimum number insertions needed to make a string palindrome ; Recursive function to find minimum number of insertions ; Base Cases ; Check if the first and last characters are same . On the basis of the comparison result , decide which subrpoblem ( s ) to call ; Driver Code
import sys NEW_LINE def findMinInsertions ( str , l , h ) : NEW_LINE INDENT if ( l > h ) : NEW_LINE INDENT return sys . maxsize NEW_LINE DEDENT if ( l == h ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT if ( l == h - 1 ) : NEW_LINE INDENT return 0 if ( str [ l ] == str [ h ] ) else 1 NEW_LINE DEDENT if ( str [ l ] == str [ h ] ) : NEW_LINE INDENT return findMinInsertions ( str , l + 1 , h - 1 ) NEW_LINE DEDENT else : NEW_LINE INDENT return ( min ( findMinInsertions ( str , l , h - 1 ) , findMinInsertions ( str , l + 1 , h ) ) + 1 ) NEW_LINE DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT str = " geeks " NEW_LINE print ( findMinInsertions ( str , 0 , len ( str ) - 1 ) ) NEW_LINE DEDENT