Ways of transforming one string to other by removing 0 or more characters
Given two sequences A, B, find out number of unique ways in sequence A, to form a subsequence of A that is identical to sequence B. Transformation is meant by converting string A (by removing 0 or more characters) to string B.
Examples:
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 Explanation : Four ways will be -> "a.b..", "a..b.", ".ab.." & ".a.b." . "." is where characters are removed.
Asked in : Google
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[0][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].
Implementation:
C++
// C++ program to count the distinct transformation // of one string to other. #include <bits/stdc++.h> using namespace std; int countTransformation(string a, string b) { int n = a.size(), m = b.size(); // If b = "" i.e., an empty string. There // is only one way to transform (remove all // characters) if (m == 0) return 1; int dp[m][n]; memset (dp, 0, sizeof (dp)); // Fill dp[][] in bottom up manner // Traverse all character of b[] for ( int i = 0; i < m; i++) { // Traverse all characters of a[] for b[i] for ( int j = i; j < n; j++) { // Filling the first row of the dp // matrix. 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]; } // Filling other rows. 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]; } // Driver code int main() { string a = "abcccdf" , b = "abccdf" ; cout << countTransformation(a, b) << endl; return 0; } |
Java
// Java program to count the // distinct transformation // of one string to other. import java.util.*; import java.io.*; class GFG { static int countTransformation(String a, String b) { int n = a.length(), m = b.length(); // If b = "" i.e., an empty string. There // is only one way to transform (remove all // characters) if (m == 0 ) { return 1 ; } int dp[][] = new int [m][n]; // Fill dp[][] in bottom up manner // Traverse all character of b[] for ( int i = 0 ; i < m; i++) { // Traverse all characters of a[] for b[i] for ( int j = i; j < n; j++) { // Filling the first row of the dp // matrix. 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 ]; } } // Filling other rows. 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 ]; } // Driver code public static void main(String[] args) { String a = "abcccdf" , b = "abccdf" ; System.out.println(countTransformation(a, b)); } } // This code is contributed by // PrinciRaj1992 |
Python3
# 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 # characters) if m = = 0 : return 1 dp = [[ 0 ] * (n) for _ in range (m)] # Fill dp[][] in bottom up manner # Traverse all character of b[] for i in range (m): # Traverse all characters of a[] for b[i] for j in range (i, n): # Filling the first row of the dp # matrix. if i = = 0 : if j = = 0 : if a[j] = = b[i]: dp[i][j] = 1 else : dp[i][j] = 0 elif a[j] = = b[i]: dp[i][j] = dp[i][j - 1 ] + 1 else : dp[i][j] = dp[i][j - 1 ] # Filling other rows 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 ] # Driver Code if __name__ = = "__main__" : a = "abcccdf" b = "abccdf" print (countTransformation(a, b)) # This code is contributed by vibhu4agarwal |
C#
// C# program to count the distinct transformation // of one string to other. using System; class GFG { static int countTransformation( string a, string b) { int n = a.Length, m = b.Length; // If b = "" i.e., an empty string. There // is only one way to transform (remove all // characters) 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; // Fill dp[][] in bottom up manner // Traverse all character of b[] for ( int i = 0; i < m; i++) { // Traverse all characters of a[] for b[i] for ( int j = i; j < n; j++) { // Filling the first row of the dp // matrix. 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]; } // Filling other rows. 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]; } // Driver code static void Main() { string a = "abcccdf" , b = "abccdf" ; Console.Write(countTransformation(a, b)); } } // This code is contributed by DrRoot_ |
Javascript
<script> // JavaScript program to count the // distinct transformation // of one string to other. function countTransformation(a,b) { var n = a.length, m = b.length; // If b = "" i.e., an empty string. There // is only one way to transform (remove all // characters) if (m == 0) { return 1; } var dp = new Array (m,n); // Fill dp[][] in bottom up manner // Traverse all character of b[] for ( var i = 0; i < m; i++) { // Traverse all characters of a[] for b[i] for ( var j = i; j < n; j++) { // Filling the first row of the dp // matrix. if (i == 1) { if (j == 1) { 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]; } } // Filling other rows. else if (a[j] == b[j]) { 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]; } // Driver code var a = "abcccdf" , b = "abccdf" ; document.write(countTransformation(a, b)); // This code is contributed by shivanisinghss2110 </script> |
Output
3
Time Complexity: O(m*n)
Auxiliary Space: O(m*n) because it is using extra space for array dp
Contact Us