Ways of transforming one string to other by removing 0 or more characters | JavaScript program to count the distinct transformation of one string to other . ; If b = " " i . e . , an empty string . There is only one way to transform ( remove all characters ) ; Fil dp [ ] [ ] in bottom up manner Traverse all character of b [ ] ; Traverse all characters of a [ ] for b [ i ] ; Filling the first row of the dp matrix . ; Filling other rows . ; Driver code
function countTransformation ( a , b ) { var n = a . length , m = b . length ; if ( m == 0 ) { return 1 ; } var dp = new Array ( m , n ) ; for ( var i = 0 ; i < m ; i ++ ) { for ( var j = i ; j < n ; j ++ ) { if ( i == 1 ) { if ( j == 1 ) { dp [ i , j ] = ( a [ j ] == b [ i ] ) ? 1 : 0 ; } else if ( a [ j ] == b [ i ] ) { dp [ i , j ] = dp [ i , j - 1 ] + 1 ; } else { dp [ i , j ] = dp [ i , j - 1 ] ; } } else if ( a [ j ] == b [ j ] ) { dp [ i , j ] = dp [ i , j - 1 ] + dp [ i - 1 , j - 1 ] ; } else { dp [ i , j ] = dp [ i , j - 1 ] ; } } } return dp [ m - 1 , n - 1 ] ; } var a = " " , b = " " ; document . write ( countTransformation ( a , b ) ) ;