Formas de transformar una string en otra eliminando 0 o más caracteres

Dadas dos secuencias A, B, averigüe el número de formas únicas en la secuencia A, para formar una subsecuencia de A que sea idéntica a la secuencia B. La transformación consiste en convertir la string A (eliminando 0 o más caracteres) en la string B.

Ejemplos:

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.

Preguntado en: Google

La idea para resolver este problema es usar Programación Dinámica. Construya una array DP 2D de tamaño m*n, donde m es el tamaño de la string B y n es el tamaño de la string A.

dp[i][j] da el número de formas de transformar la string A[0…j] en B[0…i].

• Caso 1 : dp[0][j] = 1, ya que colocar B = “” con cualquier substring de A tendría solo 1 solución, que es eliminar todos los caracteres de A.
• Caso 2: cuando i > 0, dp[i][j] puede derivarse de dos casos:
  • Caso 2.a: si B[i] != A[j], entonces la solución sería ignorar el carácter A[j] y alinear la substring B[0..i] con A[0..(j-1 )]. Por tanto, dp[i][j] = dp[i][j-1].
  • Caso 2.b: si B[i] == A[j], entonces primero podríamos tener la solución en el caso a), pero también podríamos unir los caracteres B[i] y A[j] y colocar el resto de (es decir, B[0..(i-1)] y A[0..(j-1)]. Como resultado, dp[i][j] = dp[i][j-1] + dp [i-1][j-1].

Implementación:

// 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 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];
 
        // 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 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
                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
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;
 
        // 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_

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

3

Complejidad de tiempo: O(n^2)
Complejidad de espacio: O(1)

Este artículo es una contribución de Jatin Goyal . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.