Edit Distance | DP | A Space efficient Dynamic Programming based C ++ 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 program
#include <bits/stdc++.h> NEW_LINE using namespace std ; void EditDistDP ( string str1 , string str2 ) { int len1 = str1 . length ( ) ; int len2 = str2 . length ( ) ; int DP [ 2 ] [ len1 + 1 ] ; memset ( DP , 0 , sizeof DP ) ; for ( int i = 0 ; i <= len1 ; i ++ ) DP [ 0 ] [ i ] = i ; for ( int i = 1 ; i <= len2 ; i ++ ) { for ( int j = 0 ; j <= len1 ; j ++ ) { if ( j == 0 ) DP [ i % 2 ] [ j ] = i ; else if ( 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 ] ) ) ; } } } cout << DP [ len2 % 2 ] [ len1 ] << endl ; } int main ( ) { string str1 = " food " ; string str2 = " money " ; EditDistDP ( str1 , str2 ) ; return 0 ; }