Número mínimo de eliminaciones e inserciones para transformar una string en otra

Dadas dos strings ‘str1’ y ‘str2’ de tamaño m y n respectivamente. La tarea es eliminar/borrar e insertar el número mínimo de caracteres de/en str1 para transformarlo en str2. Es posible que el mismo carácter deba eliminarse/eliminarse de un punto de str1 e insertarse en otro punto.

Ejemplo 1: 

Input : 
str1 = "heap", str2 = "pea" 
Output : 
Minimum Deletion = 2 and
Minimum Insertion = 1
Explanation:
p and h deleted from heap
Then, p is inserted at the beginning
One thing to note, though p was required yet
it was removed/deleted first from its position and
then it is inserted to some other position.
Thus, p contributes one to the deletion_count
and one to the insertion_count.

Ejemplo 2: 

Input : 
str1 = "geeksforgeeks", str2 = "geeks"
Output : 
Minimum Deletion = 8
Minimum Insertion = 0       

Enfoque sencillo:

Un enfoque simple es considerar todas las subsecuencias de str1 y para cada subsecuencia calcular las eliminaciones e inserciones mínimas para transformarlas en str2. Un método muy complejo y la complejidad temporal de esta solución es exponencial.
 

Enfoque eficiente:

Un enfoque eficiente utiliza el concepto de encontrar la longitud de la subsecuencia común más larga de las dos secuencias dadas.

Algoritmo: 

• str1 y str2 sean las strings dadas.
• m y n son sus longitudes respectivamente.
• len sea la longitud de la subsecuencia común más larga de str1 y str2
• número mínimo de eliminaciones  minDel = m – len (ya que solo necesitamos eliminar de str1 porque lo estamos reduciendo a str2)
• número mínimo de inserciones  minInsert = n – len (ya que estamos insertando x en str1, x es un número de caracteres en str2 que no forman parte de la string que es la subsecuencia común más larga)

A continuación se muestra la implementación del código anterior:

// Dynamic Programming C++ implementation to find
// minimum number of deletions and insertions
#include <bits/stdc++.h>
 
using namespace std;
 
// Returns length of longest common subsequence
// for str1[0..m-1], str2[0..n-1]
int lcs(string str1, string str2, int m, int n)
{
    int L[m + 1][n + 1];
    int i, j;
 
    // Following steps build L[m+1][n+1] in bottom
    // up fashion. Note that L[i][j] contains
    // length of LCS of str1[0..i-1] and str2[0..j-1]
    for (i = 0; i <= m; i++) {
        for (j = 0; j <= n; j++) {
            if (i == 0 || j == 0)
                L[i][j] = 0;
 
            else if (str1.at(i - 1) == str2.at(j - 1))
                L[i][j] = L[i - 1][j - 1] + 1;
 
            else
                L[i][j] = max(L[i - 1][j], L[i][j - 1]);
        }
    }
 
    // L[m][n] contains length of LCS
    // for X[0..n-1] and Y[0..m-1]
    return L[m][n];
}
 
// function to find minimum number
// of deletions and insertions
void printMinDelAndInsert(string str1, string str2)
{
    int m = str1.size();
    int n = str2.size();
 
    int len = lcs(str1, str2, m, n);
 
    cout << "Minimum number of deletions = " << (m - len)
         << endl;
 
    cout << "Minimum number of insertions = " << (n - len)
         << endl;
}
 
// Driver Code
int main()
{
    string str1 = "heap";
    string str2 = "pea";
   
      // Function Call
    printMinDelAndInsert(str1, str2);
    return 0;
}

// Dynamic Programming Java implementation
// to find minimum number of deletions and
// insertions
import java.io.*;
 
class GFG {
 
    // Returns length of length common
    // subsequence for str1[0..m-1],
    // str2[0..n-1]
    static int lcs(String str1, String str2, int m, int n)
    {
        int L[][] = new int[m + 1][n + 1];
        int i, j;
 
        // Following steps build L[m+1][n+1] in
        // bottom up fashion. Note that L[i][j]
        // contains length of LCS of str1[0..i-1]
        // and str2[0..j-1]
        for (i = 0; i <= m; i++) {
            for (j = 0; j <= n; j++) {
                if (i == 0 || j == 0)
                    L[i][j] = 0;
 
                else if (str1.charAt(i - 1)
                         == str2.charAt(j - 1))
                    L[i][j] = L[i - 1][j - 1] + 1;
 
                else
                    L[i][j] = Math.max(L[i - 1][j],
                                       L[i][j - 1]);
            }
        }
 
        // L[m][n] contains length of LCS
        // for X[0..n-1] and Y[0..m-1]
        return L[m][n];
    }
 
    // function to find minimum number
    // of deletions and insertions
    static void printMinDelAndInsert(String str1,
                                     String str2)
    {
        int m = str1.length();
        int n = str2.length();
 
        int len = lcs(str1, str2, m, n);
 
        System.out.println("Minimum number of "
                           + "deletions = ");
        System.out.println(m - len);
 
        System.out.println("Minimum number of "
                           + "insertions = ");
        System.out.println(n - len);
    }
 
    // Driver code
    public static void main(String[] args)
    {
        String str1 = new String("heap");
        String str2 = new String("pea");
       
          // Function Call
        printMinDelAndInsert(str1, str2);
    }
}
// This code is contributed by Prerna Saini

# Dynamic Programming Python3
# implementation to find minimum
# number of deletions and insertions
 
# Returns length of length
# common subsequence for
# str1[0..m-1], str2[0..n-1]
 
 
def lcs(str1, str2, m, n):
 
    L = [[0 for i in range(n + 1)]
         for i in range(m + 1)]
 
    # Following steps build L[m+1][n+1]
    # in bottom up fashion. Note that
    # L[i][j] contains length of LCS
    # of str1[0..i-1] and str2[0..j-1]
    for i in range(m + 1):
        for j in range(n + 1):
            if (i == 0 or j == 0):
                L[i][j] = 0
            elif(str1[i - 1] == str2[j - 1]):
                L[i][j] = L[i - 1][j - 1] + 1
            else:
                L[i][j] = max(L[i - 1][j],
                              L[i][j - 1])
 
    # L[m][n] contains length of LCS
    # for X[0..n-1] and Y[0..m-1]
    return L[m][n]
 
# function to find minimum number
# of deletions and insertions
 
 
def printMinDelAndInsert(str1, str2):
    m = len(str1)
    n = len(str2)
    leng = lcs(str1, str2, m, n)
    print("Minimum number of deletions = ",
          m - leng, sep=' ')
    print("Minimum number of insertions = ",
          n - leng, sep=' ')
 
 
# Driver Code
str1 = "heap"
str2 = "pea"
 
# Function Call
printMinDelAndInsert(str1, str2)
 
# This code is contributed
# by sahilshelangia

// Dynamic Programming C# implementation
// to find minimum number of deletions and
// insertions
using System;
 
class GFG {
 
    // Returns length of length common
    // subsequence for str1[0..m-1],
    // str2[0..n-1]
    static int lcs(string str1, string str2, int m, int n)
    {
        int[, ] L = new int[m + 1, n + 1];
        int i, j;
 
        // Following steps build L[m+1][n+1] in
        // bottom up fashion. Note that L[i][j]
        // contains length of LCS of str1[0..i-1]
        // and str2[0..j-1]
        for (i = 0; i <= m; i++) {
            for (j = 0; j <= n; j++) {
                if (i == 0 || j == 0)
                    L[i, j] = 0;
 
                else if (str1[i - 1] == str2[j - 1])
                    L[i, j] = L[i - 1, j - 1] + 1;
 
                else
                    L[i, j] = Math.Max(L[i - 1, j],
                                       L[i, j - 1]);
            }
        }
 
        // L[m][n] contains length of LCS
        // for X[0..n-1] and Y[0..m-1]
        return L[m, n];
    }
 
    // function to find minimum number
    // of deletions and insertions
    static void printMinDelAndInsert(string str1,
                                     string str2)
    {
        int m = str1.Length;
        int n = str2.Length;
 
        int len = lcs(str1, str2, m, n);
 
        Console.Write("Minimum number of "
                      + "deletions = ");
        Console.WriteLine(m - len);
 
        Console.Write("Minimum number of "
                      + "insertions = ");
        Console.Write(n - len);
    }
 
    // Driver code
    public static void Main()
    {
        string str1 = new string("heap");
        string str2 = new string("pea");
       
          // Function Call
        printMinDelAndInsert(str1, str2);
    }
}
 
// This code is contributed by nitin mittal.

<script>
    // Dynamic Programming Javascript implementation
    // to find minimum number of deletions and
    // insertions
 
    // Returns length of length common
    // subsequence for str1[0..m-1],
    // str2[0..n-1]
    function lcs(str1, str2, m, n)
    {
        let L = new Array(m + 1);
             
        let i, j;
         
        for (i = 0; i <= m; i++)
        {
            L[i] = new Array(n + 1);
            for (j = 0; j <= n; j++)
            {
                L[i][j] = 0;
            }
        }
  
        // Following steps build L[m+1][n+1] in
        // bottom up fashion. Note that L[i][j]
        // contains length of LCS of str1[0..i-1]
        // and str2[0..j-1]
        for (i = 0; i <= m; i++) {
            for (j = 0; j <= n; j++) {
                if (i == 0 || j == 0)
                    L[i][j] = 0;
  
                else if (str1[i - 1]
                         == str2[j - 1])
                    L[i][j] = L[i - 1][j - 1] + 1;
  
                else
                    L[i][j] = Math.max(L[i - 1][j],
                                       L[i][j - 1]);
            }
        }
  
        // L[m][n] contains length of LCS
        // for X[0..n-1] and Y[0..m-1]
        return L[m][n];
    }
  
    // function to find minimum number
    // of deletions and insertions
    function printMinDelAndInsert(str1, str2)
    {
        let m = str1.length;
        let n = str2.length;
  
        let len = lcs(str1, str2, m, n);
  
        document.write("Minimum number of "
                           + "deletions = ");
        document.write((m - len) + "</br>");
  
        document.write("Minimum number of "
                           + "insertions = ");
        document.write((n - len) + "</br>");
    }
     
    let str1 = "heap";
    let str2 = "pea";
 
    // Function Call
    printMinDelAndInsert(str1, str2);
     
    // This code is contributed by rameshtravel07.
</script>

Minimum number of deletions = 2
Minimum number of insertions = 1

Complejidad temporal: O(m * n)

Método 2: enfoque de arriba hacia abajo usando memorización

Este método también utiliza la idea de encontrar la longitud de la subsecuencia común más larga de las dos secuencias dadas. Pero este enfoque utiliza un enfoque de arriba hacia abajo utilizando la memorización.

// Dynamic Programming C++ implementation to find
// minimum number of deletions and insertions
// using memoization technique
#include <bits/stdc++.h>
 
using namespace std;
 
int dp[1001][1001];
 
// Returns length of longest common subsequence
int lcs(string& s1, string& s2, int i, int j)
{
    if (i == 0 || j == 0) {
        return 0;
    }
    if (dp[i][j] != -1) {
        return dp[i][j];
    }
    if (s1[i - 1] == s2[j - 1]) {
        return dp[i][j] = 1 + lcs(s1, s2, i - 1, j - 1);
    }
    else {
        return dp[i][j] = max(lcs(s1, s2, i, j - 1),
                              lcs(s1, s2, i - 1, j));
    }
}
 
// function to find minimum number
// of deletions and insertions
void printMinDelAndInsert(string str1, string str2)
{
    int m = str1.size();
    int n = str2.size();
 
    dp[m][n];
 
    //    initialising dp array as -1
    memset(dp, -1, sizeof(dp));
 
    int len = lcs(str1, str2, m, n);
 
    cout << "Minimum number of deletions = " << (m - len)
         << endl;
 
    cout << "Minimum number of insertions = " << (n - len)
         << endl;
}
 
// driver code
int main()
{
    string str1 = "heap";
    string str2 = "pea";
 
    // Function Call
    printMinDelAndInsert(str1, str2);
 
    return 0;
}
 
// This code is contributed by Arun Bang.

Minimum number of deletions = 2
Minimum number of insertions = 1

Complejidad temporal: O(m * n)
Este artículo es una contribución de Ayush Jauhari . 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.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.