Ways of transforming one string to other by removing 0 or more characters | Java 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
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 = i ; j < n ; j ++ ) { if ( i == 0 ) { if ( j == 0 ) { dp [ i ] [ j ] = ( a . charAt ( j ) == b . charAt ( i ) ) ? 1 : 0 ; } else if ( a . charAt ( j ) == b . charAt ( i ) ) { dp [ i ] [ j ] = dp [ i ] [ j - 1 ] + 1 ; } else { dp [ i ] [ j ] = dp [ i ] [ j - 1 ] ; } } else if ( a . charAt ( j ) == b . charAt ( 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 ] ; } public static void main ( String [ ] args ) { String a = " abcccdf " , b = " abccdf " ; System . out . println ( countTransformation ( a , b ) ) ; } }