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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int countTransformation ( string a , string b ) { int n = a . size ( ) , m = b . size ( ) ; if ( m == 0 ) return 1 ; int dp [ m ] [ n ] ; memset ( dp , 0 , sizeof ( dp ) ) ; 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 ] ; } int main ( ) { string a = " abcccdf " , b = " abccdf " ; cout << countTransformation ( a , b ) << endl ; return 0 ; }