Ways of transforming one string to other by removing 0 or more characters | Python3 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 ) ; Fill 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
def countTransformation ( a , b ) : NEW_LINE INDENT n = len ( a ) NEW_LINE m = len ( b ) NEW_LINE if m == 0 : NEW_LINE INDENT return 1 NEW_LINE DEDENT dp = [ [ 0 ] * ( n ) for _ in range ( m ) ] NEW_LINE for i in range ( m ) : NEW_LINE INDENT for j in range ( i , n ) : NEW_LINE INDENT if i == 0 : NEW_LINE INDENT if j == 0 : NEW_LINE INDENT if a [ j ] == b [ i ] : NEW_LINE INDENT dp [ i ] [ j ] = 1 NEW_LINE DEDENT else : NEW_LINE INDENT dp [ i ] [ j ] = 0 NEW_LINE DEDENT DEDENT elif a [ j ] == b [ i ] : NEW_LINE INDENT dp [ i ] [ j ] = dp [ i ] [ j - 1 ] + 1 NEW_LINE DEDENT else : NEW_LINE INDENT dp [ i ] [ j ] = dp [ i ] [ j - 1 ] NEW_LINE DEDENT DEDENT else : NEW_LINE INDENT if a [ j ] == b [ i ] : NEW_LINE INDENT dp [ i ] [ j ] = ( dp [ i ] [ j - 1 ] + dp [ i - 1 ] [ j - 1 ] ) NEW_LINE DEDENT else : NEW_LINE INDENT dp [ i ] [ j ] = dp [ i ] [ j - 1 ] NEW_LINE DEDENT DEDENT DEDENT DEDENT return dp [ m - 1 ] [ n - 1 ] NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT a = " abcccdf " NEW_LINE b = " abccdf " NEW_LINE print ( countTransformation ( a , b ) ) NEW_LINE DEDENT