Minimum Cost To Make Two Strings Identical | Returns length of LCS for X [ 0. . m - 1 ] , Y [ 0. . n - 1 ] ; Following steps build L [ m + 1 ] [ n + 1 ] in bottom up fashion . Note that L [ i ] [ j ] contains length of LCS of X [ 0. . i - 1 ] and Y [ 0. . j - 1 ] ; L [ m ] [ n ] contains length of LCS for X [ 0. . n - 1 ] and Y [ 0. . m - 1 ] ; Returns cost of making X [ ] and Y [ ] identical . costX is cost of removing a character from X [ ] and costY is cost of removing a character from Y [ ] / ; Find LCS of X [ ] and Y [ ] ; Cost of making two strings identical is SUM of following two 1 ) Cost of removing extra characters from first string 2 ) Cost of removing extra characters from second string ; Driver code
function lcs ( X , Y , m , n ) { let L = new Array ( m + 1 ) ; for ( let i = 0 ; i < m + 1 ; i ++ ) { L [ i ] = new Array ( n + 1 ) ; } for ( let i = 0 ; i < m + 1 ; i ++ ) { for ( let j = 0 ; j < n + 1 ; j ++ ) { L [ i ] [ j ] = 0 ; } } for ( let i = 0 ; i <= m ; i ++ ) { for ( let j = 0 ; j <= n ; j ++ ) { if ( i == 0 j == 0 ) L [ i ] [ j ] = 0 ; else if ( X [ i - 1 ] == Y [ j - 1 ] ) L [ i ] [ j ] = L [ i - 1 ] [ j - 1 ] + 1 ; else L [ i ] [ j ] = Math . max ( L [ i - 1 ] [ j ] , L [ i ] [ j - 1 ] ) ; } } return L [ m ] [ n ] ; } function findMinCost ( X , Y , costX , costY ) { let m = X . length ; let n = Y . length ; let len_LCS ; len_LCS = lcs ( X , Y , m , n ) ; return costX * ( m - len_LCS ) + costY * ( n - len_LCS ) ; } let X = " " ; let Y = " " ; document . write ( " " + " " + findMinCost ( X , Y , 10 , 20 ) ) ;