Ways of transforming one string to other by removing 0 or more characters | C # 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
using System ; class GFG { static int countTransformation ( string a , string b ) { int n = a . Length , m = b . Length ; if ( m == 0 ) return 1 ; int [ , ] dp = new int [ m , n ] ; for ( int i = 0 ; i < m ; i ++ ) for ( int j = 0 ; j < n ; j ++ ) dp [ i , j ] = 0 ; for ( int i = 0 ; i < m ; i ++ ) { for ( int j = i ; j < n ; j ++ ) { if ( i == 0 ) { if ( j == 0 ) 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 [ i ] ) 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 ] ; } static void Main ( ) { string a = " abcccdf " , b = " abccdf " ; Console . Write ( countTransformation ( a , b ) ) ; } }