human
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"
Solution in Python:
 ... Can you provide a code to edit Distance and the other steps required?
assistant
#Here is code to edit Distance and the other steps required.
 def EditDistDP ( str1 , str2 ) :
	len1 = len ( str1 )
	len2 = len ( str2 )
	DP = [ [ 0 for i in range ( len1 + 1 ) ] for j in range ( 2 ) ] ;
	for i in range ( 0 , len1 + 1 ) :
		DP [ 0 ] [ i ] = i
	for i in range ( 1 , len2 + 1 ) :
		for j in range ( 0 , len1 + 1 ) :
			if ( j == 0 ) :
				DP [ i % 2 ] [ j ] = i
			elif ( str1 [ j - 1 ] == str2 [ i - 1 ] ) :
				DP [ i % 2 ] [ j ] = DP [ ( i - 1 ) % 2 ] [ j - 1 ]
			else :
				DP [ i % 2 ] [ j ] = ( 1 + min ( DP [ ( i - 1 ) % 2 ] [ j ] , min ( DP [ i % 2 ] [ j - 1 ] , DP [ ( i - 1 ) % 2 ] [ j - 1 ] ) ) )
	print ( DP [ len2 % 2 ] [ len1 ] , " " )
if __name__ == ' _ _ main _ _ ' :
	str1 = " food "
	str2 = " money "
	EditDistDP ( str1 , str2 )