通过删除0个或多个字符将一个字符串转换为其他字符串的方法

本文概述

C ++
Java
Python3
C#

【通过删除0个或多个字符将一个字符串转换为其他字符串的方法】给定两个序列A, B, 找出序列A中许多独特的方式, 以形成与序列B相同的A子序列。转换的意思是将字符串A(通过删除0个或多个字符)转换为字符串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.

询问：谷歌
解决此问题的想法是使用动态编程。构造一个m * n大小的2D DP矩阵, 其中m是字符串B的大小, n是字符串A的大小。
dp [i] [j]给出了将字符串A [0…j]转换为B [0…i]的方式的数量。
情况1：dp [0] [j] = 1, 因为将B =""与A的任何子字符串一起放置将只有一种解决方案, 即删除A中的所有字符。
情况2：当i> 0时, 可以通过两种情况得出dp [i] [j]：

情况2.a：如果B [i]！= A [j], 则解决方案是忽略字符A [j], 并将子字符串B [0..i]与A [0 ..(j-1)]对齐。因此, dp [i] [j] = dp [i] [j-1]。
情况2.b：如果B [i] == A [j], 那么首先我们可以得到情况a)的解, 但是我们也可以匹配字符B [i]和A [j]并放置其余的字符(即B [ 0 ..(i-1)]和A [0 ..(j-1)]。结果, dp [i] [j] = dp [i] [j-1] + dp [i-1] [j-1]。

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)); // Fil dp[][] in bottom up manner // Traverse all character of b[] for ( int i = 0; i < m; i++) {// Traverse all charaters 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. 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]; // Fil dp[][] in bottom up manner // Traverse all character of b[] for ( int i = 0 ; i < m; i++) {// Traverse all charaters 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 1dp = [[ 0 ] * (n) for _ in range (m)]# 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 # 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# 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; // Fil 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_

输出如下：