Edit Distance | DP | A Space efficient Dynamic Programming based Javascript 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
function EditDistDP ( str1 , str2 ) { let len1 = str1 . length ; let len2 = str2 . length ; let DP = new Array ( 2 ) ; for ( let i = 0 ; i < 2 ; i ++ ) { DP [ i ] = new Array ( len1 + 1 ) ; for ( let j = 0 ; j < len1 + 1 ; j ++ ) DP [ i ] [ j ] = 0 ; } for ( let i = 0 ; i <= len1 ; i ++ ) DP [ 0 ] [ i ] = i ; for ( let i = 1 ; i <= len2 ; i ++ ) { for ( let 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 + Math . min ( DP [ ( i - 1 ) % 2 ] [ j ] , Math . min ( DP [ i % 2 ] [ j - 1 ] , DP [ ( i - 1 ) % 2 ] [ j - 1 ] ) ) ; } } } document . write ( DP [ len2 % 2 ] [ len1 ] + " " ) ; } let str1 = " " ; let str2 = " " ; EditDistDP ( str1 , str2 ) ;