Edit Distance | DP |  ; If any string is empty , return the remaining characters of other string ; To check if the recursive tree for given n & m has already been executed ; If characters are equal , execute recursive function for n - 1 , m - 1 ; If characters are nt equal , we need to find the minimum cost out of all 3 operations . ; temp variables ; Driver code
def minDis ( s1 , s2 , n , m , dp ) : NEW_LINE INDENT if ( n == 0 ) : NEW_LINE INDENT return m NEW_LINE DEDENT if ( m == 0 ) : NEW_LINE INDENT return n NEW_LINE DEDENT if ( dp [ n ] [ m ] != - 1 ) : NEW_LINE INDENT return dp [ n ] [ m ] ; NEW_LINE DEDENT if ( s1 [ n - 1 ] == s2 [ m - 1 ] ) : NEW_LINE INDENT if ( dp [ n - 1 ] [ m - 1 ] == - 1 ) : NEW_LINE INDENT dp [ n ] [ m ] = minDis ( s1 , s2 , n - 1 , m - 1 , dp ) NEW_LINE return dp [ n ] [ m ] NEW_LINE DEDENT else : NEW_LINE INDENT dp [ n ] [ m ] = dp [ n - 1 ] [ m - 1 ] NEW_LINE return dp [ n ] [ m ] NEW_LINE DEDENT DEDENT else : NEW_LINE INDENT if ( dp [ n - 1 ] [ m ] != - 1 ) : NEW_LINE m1 = dp [ n - 1 ] [ m ] NEW_LINE else : NEW_LINE m1 = minDis ( s1 , s2 , n - 1 , m , dp ) NEW_LINE if ( dp [ n ] [ m - 1 ] != - 1 ) : NEW_LINE m2 = dp [ n ] [ m - 1 ] NEW_LINE else : NEW_LINE m2 = minDis ( s1 , s2 , n , m - 1 , dp ) NEW_LINE if ( dp [ n - 1 ] [ m - 1 ] != - 1 ) : NEW_LINE m3 = dp [ n - 1 ] [ m - 1 ] NEW_LINE else : NEW_LINE m3 = minDis ( s1 , s2 , n - 1 , m - 1 , dp ) NEW_LINE dp [ n ] [ m ] = 1 + min ( m1 , min ( m2 , m3 ) ) NEW_LINE return dp [ n ] [ m ] NEW_LINE DEDENT DEDENT str1 = " voldemort " NEW_LINE str2 = " dumbledore " NEW_LINE n = len ( str1 ) NEW_LINE m = len ( str2 ) NEW_LINE dp = [ [ - 1 for i in range ( m + 1 ) ] for j in range ( n + 1 ) ] NEW_LINE print ( minDis ( str1 , str2 , n , m , dp ) ) NEW_LINE