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

2021年4月4日19:41:47 发表评论 558 次浏览

## 本文概述

``````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.``````

dp [i] [j]给出了将字符串A [0…j]转换为B [0…i]的方式的数量。

• 情况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 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 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#

``````// 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_``````

``3``