Edit Distance | DP | A Space efficient Dynamic Programming based Python3 program to find minimum number operations to convert str1 to str2 ; Create a DP array to memoize result of previous computations ; Base condition when second String is empty then we remove all characters ; Start filling the DP This loop run for every character in second String ; This loop compares the char from second String with first String characters ; If first String is empty then we have to perform add character operation to get second String ; If character from both String is same then we do not perform any operation . here i % 2 is for bound the row number . ; If character from both String is not same then we take the minimum from three specified operation ; After complete fill the DP array if the len2 is even then we end up in the 0 th row else we end up in the 1 th row so we take len2 % 2 to get row ; Driver code
def EditDistDP ( str1 , str2 ) : NEW_LINE INDENT len1 = len ( str1 ) NEW_LINE len2 = len ( str2 ) NEW_LINE DP = [ [ 0 for i in range ( len1 + 1 ) ] for j in range ( 2 ) ] ; NEW_LINE for i in range ( 0 , len1 + 1 ) : NEW_LINE INDENT DP [ 0 ] [ i ] = i NEW_LINE DEDENT for i in range ( 1 , len2 + 1 ) : NEW_LINE INDENT for j in range ( 0 , len1 + 1 ) : NEW_LINE INDENT if ( j == 0 ) : NEW_LINE INDENT DP [ i % 2 ] [ j ] = i NEW_LINE DEDENT elif ( str1 [ j - 1 ] == str2 [ i - 1 ] ) : NEW_LINE INDENT DP [ i % 2 ] [ j ] = DP [ ( i - 1 ) % 2 ] [ j - 1 ] NEW_LINE DEDENT else : NEW_LINE INDENT DP [ i % 2 ] [ j ] = ( 1 + min ( DP [ ( i - 1 ) % 2 ] [ j ] , min ( DP [ i % 2 ] [ j - 1 ] , DP [ ( i - 1 ) % 2 ] [ j - 1 ] ) ) ) NEW_LINE DEDENT DEDENT DEDENT print ( DP [ len2 % 2 ] [ len1 ] , " " ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT str1 = " food " NEW_LINE str2 = " money " NEW_LINE EditDistDP ( str1 , str2 ) NEW_LINE DEDENT