En la distancia de edición estándar, donde se nos permiten 3 operaciones, insertar, eliminar y reemplazar. Considere una variación de la distancia de edición en la que solo se permiten dos operaciones, insertar y eliminar, encuentre la distancia de edición en esta variación.
Ejemplos:
Input : str1 = "cat", st2 = "cut" Output : 2 We are allowed to insert and delete. We delete 'a' from "cat" and insert "u" to make it "cut". Input : str1 = "acb", st2 = "ab" Output : 1 We can convert "acb" to "ab" by removing 'c'.
Una solución es simplemente modificar la Solución de edición de distancia haciendo dos llamadas recursivas en lugar de tres. Una solución interesante se basa en LCS.
1) Encuentra LCS de dos strings. Sea x la longitud de LCS .
2) Sea m la longitud de la primera cuerda y n la longitud de la segunda cuerda . Nuestro resultado es (m – x) + (n – x). Básicamente necesitamos hacer (m – x) operaciones de eliminación y (n – x) operaciones de inserción.
C++
// CPP program to find Edit Distance (when only two
// operations are allowed, insert and delete) using LCS.
#include<bits/stdc++.h>
using namespace std;
int editDistanceWith2Ops(string &X, string &Y)
{
// Find LCS
int m = X.length(), n = Y.length();
int L[m+1][n+1];
for (int i=0; i<=m; i++)
{
for (int j=0; j<=n; j++)
{
if (i == 0 || j == 0)
L[i][j] = 0;
else if (X[i-1] == Y[j-1])
L[i][j] = L[i-1][j-1] + 1;
else
L[i][j] = max(L[i-1][j], L[i][j-1]);
}
}
int lcs = L[m][n];
// Edit distance is delete operations +
// insert operations.
return (m - lcs) + (n - lcs);
}
/* Driver program to test above function */
int main()
{
string X = "abc", Y = "acd";
cout << editDistanceWith2Ops(X, Y);
return 0;
}
Java
//Java program to find Edit Distance (when only two
// operations are allowed, insert and delete) using LCS.
class GFG {
static int editDistanceWith2Ops(String X, String Y) {
// Find LCS
int m = X.length(), n = Y.length();
int L[][] = new int[m + 1][n + 1];
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
if (i == 0 || j == 0) {
L[i][j] = 0;
} else if (X.charAt(i - 1) == Y.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]);
}
}
}
int lcs = L[m][n];
// Edit distance is delete operations +
// insert operations.
return (m - lcs) + (n - lcs);
}
/* Driver program to test above function */
public static void main(String[] args) {
String X = "abc", Y = "acd";
System.out.println(editDistanceWith2Ops(X, Y));
}
}
/* This Java code is contributed by 29AjayKumar*/
Python 3
# Python 3 program to find Edit Distance # (when only two operations are allowed, # insert and delete) using LCS. def editDistanceWith2Ops(X, Y): # Find LCS m = len(X) n = len(Y) L = [[0 for x in range(n + 1)] for y in range(m + 1)] for i in range(m + 1): for j in range(n + 1): if (i == 0 or j == 0): L[i][j] = 0 elif (X[i - 1] == Y[j - 1]): L[i][j] = L[i - 1][j - 1] + 1 else: L[i][j] = max(L[i - 1][j], L[i][j - 1]) lcs = L[m][n] # Edit distance is delete operations + # insert operations. return (m - lcs) + (n - lcs) # Driver Code if __name__ == "__main__": X = "abc" Y = "acd" print(editDistanceWith2Ops(X, Y)) # This code is contributed by ita_c
C#
// C# program to find Edit Distance
// (when only two operations are
// allowed, insert and delete) using LCS.
using System;
class GFG
{
static int editDistanceWith2Ops(String X,
String Y)
{
// Find LCS
int m = X.Length, n = Y.Length;
int [ , ]L = new int[m + 1 , n + 1];
for (int i = 0; i <= m; i++)
{
for (int j = 0; j <= n; j++)
{
if (i == 0 || j == 0)
{
L[i , j] = 0;
}
else if (X[i - 1] == Y[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]);
}
}
}
int lcs = L[m , n];
// Edit distance is delete operations +
// insert operations.
return (m - lcs) + (n - lcs);
}
// Driver Code
public static void Main()
{
String X = "abc", Y = "acd";
Console.Write(editDistanceWith2Ops(X, Y));
}
}
// This code is contributed
// by 29AjayKumar
PHP
<?php
// PHP program to find Edit Distance
// (when only two operations are allowed,
// insert and delete) using LCS.
function editDistanceWith2Ops($X, $Y)
{
// Find LCS
$m = strlen($X); $n = strlen($Y);
$L[$m + 1][$n + 1];
for ($i = 0; $i <= $m; $i++)
{
for ($j = 0; $j <= $n; $j++)
{
if ($i == 0 || $j == 0)
$L[$i][$j] = 0;
else if ($X[$i - 1] == $Y[$j - 1])
$L[$i][$j] = $L[$i - 1][$j - 1] + 1;
else
$L[$i][$j] = max($L[$i - 1][$j],
$L[$i][$j - 1]);
}
}
$lcs = $L[$m][$n];
// Edit distance is delete operations +
// insert operations.
return ($m - $lcs) + ($n - $lcs);
}
// Driver Code
$X = "abc"; $Y = "acd";
echo editDistanceWith2Ops($X, $Y);
// This code is contributed
// by Akanksha Rai
?>
Javascript
<script>
//Javascript program to find Edit Distance (when only two
// operations are allowed, insert and delete) using LCS.
function editDistanceWith2Ops(X,Y)
{
// Find LCS
let m = X.length, n = Y.length;
let L = new Array(m + 1);
for(let i=0;i<L.length;i++)
{
L[i]=new Array(n+1);
for(let j=0;j<L[i].length;j++)
{
L[i][j]=0;
}
}
for (let i = 0; i <= m; i++) {
for (let j = 0; j <= n; j++) {
if (i == 0 || j == 0) {
L[i][j] = 0;
} else if (X[i-1] == Y[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]);
}
}
}
let lcs = L[m][n];
// Edit distance is delete operations +
// insert operations.
return (m - lcs) + (n - lcs);
}
/* Driver program to test above function */
let X = "abc", Y = "acd";
document.write(editDistanceWith2Ops(X, Y));
// This code is contributed by rag2127
</script>
Producción:
2
Tiempo Complejidad: O(m * n)
Espacio Auxiliar: O(m * n)