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

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

本文概述

给定两个序列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)

如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。

木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: