Given two sequences A, B, find out number of unique ways in sequence A, to form a subsequence of A that is identical to the sequence B. Transformation is meant by converting string A (by removing 0 or more characters) to string B.
Input : A = "abcccdf", B = "abccdf" Output : 3 Explanation : Three ways will be -> "ab.ccdf", "abc.cdf" & "abcc.df" . "." is where character is removed. Input : A = "aabba", B = "ab" Output : 4 Expalnation : Four ways will be -> "a.b..", "a..b.", ".ab.." & ".a.b." . "." is where characters are removed.
Asked in :
The idea to solve this problem is using Dynamic Programming. Construct a 2D DP matrix of m*n size, where m is size of string B and n is size of string A.
dp[i][j] gives the number of ways of transforming string A[0…j] to B[0…i].
- Case 1 : dp[j] = 1, since placing B = “” with any substring of A would have only 1 solution which is to delete all characters in A.
- Case 2 : when i > 0, dp[i][j] can be derived by two cases:
- Case 2.a : if B[i] != A[j], then the solution would be to ignore the character A[j] and align substring B[0..i] with A[0..(j-1)]. Therefore, dp[i][j] = dp[i][j-1].
- Case 2.b : if B[i] == A[j], then first we could have the solution in case a), but also we could match the characters B[i] and A[j] and place the rest of them (i.e. B[0..(i-1)] and A[0..(j-1)]. As a result, dp[i][j] = dp[i][j-1] + dp[i-1][j-1].
# Python3 program to count the distinct
# transformation of one string to other.
def countTransformation(a, b):
n = len(a)
m = len(b)
# If b = “” i.e., an empty string. There
# is only one way to transform (remove all
if m == 0:
dp = [ * (n + 1) for _ in range(m + 1)]
# Fill dp in bottom up manner
# Traverse all character of b
for i in range(m):
# Traverse all charaters of a for b[i]
for j in range(i, n):
# Filling the first row of the dp
if i == 0:
if a[j] == b[i] and j == 0:
dp[i][j] = 1
elif a[j] == b[i]:
dp[i][j] = dp[i][j – 1] + 1
dp[i][j] = dp[i][j – 1]
# Filling other rows
if a[j] == b[i]:
dp[i][j] = (dp[i][j – 1] +
dp[i – 1][j – 1])
dp[i][j] = dp[i][j – 1]
return dp[m – 1][n – 1]
# Driver Code
if __name__ == “__main__”:
a = “abcccdf”
b = “abccdf”
# This code is contributed by vibhu4agarwal
Time Complexity: O(n^2)
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
This article is attributed to GeeksforGeeks.org