本文概述
给定两个序列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 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
时间复杂度:O(n ^ 2)
如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。