Prerrequisito: Programación Dinámica | Conjunto 5 (Editar distancia)
Dadas dos strings str1 y str2, la tarea es imprimir todas las formas posibles de convertir ‘str1’ en ‘str2’.
A continuación se muestran las operaciones que se pueden realizar en «str1»:
- Insertar
- Remover
- Reemplazar
Todas las operaciones anteriores son de igual costo. La tarea es imprimir todas las diversas formas de convertir ‘str1’ en ‘str2’ usando el número mínimo de ediciones (operaciones) requeridas, donde una «forma» se compone de la serie de todas las operaciones requeridas.
Ejemplos:
Entrada: str1 = “abcdef”, str2 = “axcdfdh”
Salida:
Método 1:
Agregar h
Cambiar f por d
Cambiar e por f
Cambiar b por x
Método 2:
Cambiar f por h
Agregar d
Cambiar e por f
Cambiar b por x
Método 3:
Cambie f por h
Cambie e por d
Agregue f
Cambie b por x
Enfoque para imprimir una forma posible:
El enfoque para encontrar el número mínimo de ediciones se ha discutido en esta publicación . Para imprimir de una forma posible, itere desde la esquina inferior derecha de la array DP formada con el método Distancia mínima de edición . Compruebe si el carácter perteneciente a ese elemento en ambas strings es igual o no. Si es así, significa que no necesita edición y DP[i][j] se copió de DP[i-1][j-1].
If str1[i-1] == str2[j-1], proceed diagonally.
Tenga en cuenta que dado que la array DP contiene una fila y una columna adicionales en los índices 0, los índices de string se reducirán en uno. es decir, DP[i][j] corresponde al índice i-1 de str1 y al índice j-1 de str2.
Ahora bien, si los caracteres no fueran iguales, eso significa que este elemento de la array DP[i][j] se obtuvo del mínimo de DP[i-1][j-1], DP[i][j-1] y DP [i-1][j], más 1. Por lo tanto, verifique de dónde proviene este elemento.
1. If DP[i][j] == DP[i-1][j-1] + 1
It means the character was replaced from str1[i] to str2[j]. Proceed diagonally.
2. If DP[i][j] == DP[i][j-1] + 1
It means the character was Added from str2[j]. Proceed left.
3. If DP[i][j] == DP[i-1][j] + 1
It means the character str1[i] was deleted. Proceed up.
Una vez que se alcanza el final, es decir, (i==0 o j==0) de cualquiera de las strings, se realiza la conversión de una string a otra. Habremos impreso todo el conjunto de operaciones necesarias.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to print one possible
// way of converting a string to another
#include <bits/stdc++.h>
using namespace std;
int DP[100][100];
// Function to print the steps
void printChanges(string s1, string s2,
int dp[][100])
{
int i = s1.length();
int j = s2.length();
// check till the end
while (i and j)
{
// if characters are same
if (s1[i - 1] == s2[j - 1])
{
i--;
j--;
}
// Replace
else if (dp[i][j] == dp[i - 1][j - 1] + 1)
{
cout << "change " << s1[i - 1]
<< " to " << s2[j - 1] << endl;
i--;
j--;
}
// Delete the character
else if (dp[i][j] == dp[i - 1][j] + 1)
{
cout << "Delete " << s1[i - 1] << endl;
i--;
}
// Add the character
else if (dp[i][j] == dp[i][j - 1] + 1)
{
cout << "Add " << s2[j - 1] << endl;
j--;
}
}
}
// Function to compute the DP matrix
void editDP(string s1, string s2)
{
int l1 = s1.length();
int l2 = s2.length();
DP[l1 + 1][l2 + 1];
// initialize by the maximum edits possible
for (int i = 0; i <= l1; i++)
DP[i][0] = i;
for (int j = 0; j <= l2; j++)
DP[0][j] = j;
// Compute the DP matrix
for (int i = 1; i <= l1; i++)
{
for (int j = 1; j <= l2; j++)
{
// if the characters are same
// no changes required
if (s1[i - 1] == s2[j - 1])
DP[i][j] = DP[i - 1][j - 1];
else
// minimum of three operations possible
DP[i][j] = min(min(DP[i - 1][j - 1],
DP[i - 1][j]),
DP[i][j - 1]) + 1;
}
}
// print the steps
printChanges(s1, s2, DP);
}
// Driver Code
int main()
{
string s1 = "abcdef";
string s2 = "axcdfdh";
// calculate the DP matrix
editDP(s1, s2);
return 0;
}
// This code is contributed by
// sanjeev2552
Java
// Java program to print one possible
// way of converting a string to another
import java.util.*;
public class Edit_Distance {
static int dp[][];
// Function to print the steps
static void printChanges(String s1, String s2)
{
int i = s1.length();
int j = s2.length();
// check till the end
while (i != 0 && j != 0) {
// if characters are same
if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
i--;
j--;
}
// Replace
else if (dp[i][j] == dp[i - 1][j - 1] + 1) {
System.out.println("change " + s1.charAt(i - 1) + " to " + s2.charAt(j - 1));
i--;
j--;
}
// Delete the character
else if (dp[i][j] == dp[i - 1][j] + 1) {
System.out.println("Delete " + s1.charAt(i - 1));
i--;
}
// Add the character
else if (dp[i][j] == dp[i][j - 1] + 1) {
System.out.println("Add " + s2.charAt(j - 1));
j--;
}
}
}
// Function to compute the DP matrix
static void editDP(String s1, String s2)
{
int l1 = s1.length();
int l2 = s2.length();
int[][] DP = new int[l1 + 1][l2 + 1];
// initialize by the maximum edits possible
for (int i = 0; i <= l1; i++)
DP[i][0] = i;
for (int j = 0; j <= l2; j++)
DP[0][j] = j;
// Compute the DP matrix
for (int i = 1; i <= l1; i++) {
for (int j = 1; j <= l2; j++) {
// if the characters are same
// no changes required
if (s1.charAt(i - 1) == s2.charAt(j - 1))
DP[i][j] = DP[i - 1][j - 1];
else {
// minimum of three operations possible
DP[i][j] = min(DP[i - 1][j - 1],
DP[i - 1][j], DP[i][j - 1])
+ 1;
}
}
}
// initialize to global array
dp = DP;
}
// Function to find the minimum of three
static int min(int a, int b, int c)
{
int z = Math.min(a, b);
return Math.min(z, c);
}
// Driver Code
public static void main(String[] args) throws Exception
{
String s1 = "abcdef";
String s2 = "axcdfdh";
// calculate the DP matrix
editDP(s1, s2);
// print the steps
printChanges(s1, s2);
}
}
Python3
# Python3 program to print one possible
# way of converting a string to another
# Function to print the steps
def printChanges(s1, s2, dp):
i = len(s1)
j = len(s2)
# Check till the end
while(i > 0 and j > 0):
# If characters are same
if s1[i - 1] == s2[j - 1]:
i -= 1
j -= 1
# Replace
elif dp[i][j] == dp[i - 1][j - 1] + 1:
print("change", s1[i - 1],
"to", s2[j - 1])
j -= 1
i -= 1
# Delete
elif dp[i][j] == dp[i - 1][j] + 1:
print("Delete", s1[i - 1])
i -= 1
# Add
elif dp[i][j] == dp[i][j - 1] + 1:
print("Add", s2[j - 1])
j -= 1
# Function to compute the DP matrix
def editDP(s1, s2):
len1 = len(s1)
len2 = len(s2)
dp = [[0 for i in range(len2 + 1)]
for j in range(len1 + 1)]
# Initialize by the maximum edits possible
for i in range(len1 + 1):
dp[i][0] = i
for j in range(len2 + 1):
dp[0][j] = j
# Compute the DP Matrix
for i in range(1, len1 + 1):
for j in range(1, len2 + 1):
# If the characters are same
# no changes required
if s2[j - 1] == s1[i - 1]:
dp[i][j] = dp[i - 1][j - 1]
# Minimum of three operations possible
else:
dp[i][j] = 1 + min(dp[i][j - 1],
dp[i - 1][j - 1],
dp[i - 1][j])
# Print the steps
printChanges(s1, s2, dp)
# Driver Code
s1 = "abcdef"
s2 = "axcdfdh"
# Compute the DP Matrix
editDP(s1, s2)
# This code is contributed by Pranav S
C#
// C# program to print one possible
// way of converting a string to another
using System;
public class Edit_Distance
{
static int [,]dp;
// Function to print the steps
static void printChanges(String s1, String s2)
{
int i = s1.Length;
int j = s2.Length;
// check till the end
while (i != 0 && j != 0)
{
// if characters are same
if (s1[i - 1] == s2[j - 1])
{
i--;
j--;
}
// Replace
else if (dp[i, j] == dp[i - 1, j - 1] + 1)
{
Console.WriteLine("change " + s1[i - 1] + " to " + s2[j - 1]);
i--;
j--;
}
// Delete the character
else if (dp[i, j] == dp[i - 1, j] + 1)
{
Console.WriteLine("Delete " + s1[i - 1]);
i--;
}
// Add the character
else if (dp[i, j] == dp[i, j - 1] + 1)
{
Console.WriteLine("Add " + s2[j - 1]);
j--;
}
}
}
// Function to compute the DP matrix
static void editDP(String s1, String s2)
{
int l1 = s1.Length;
int l2 = s2.Length;
int[,] DP = new int[l1 + 1, l2 + 1];
// initialize by the maximum edits possible
for (int i = 0; i <= l1; i++)
DP[i, 0] = i;
for (int j = 0; j <= l2; j++)
DP[0, j] = j;
// Compute the DP matrix
for (int i = 1; i <= l1; i++)
{
for (int j = 1; j <= l2; j++)
{
// if the characters are same
// no changes required
if (s1[i - 1] == s2[j - 1])
DP[i, j] = DP[i - 1, j - 1];
else
{
// minimum of three operations possible
DP[i, j] = min(DP[i - 1, j - 1],
DP[i - 1, j], DP[i, j - 1])
+ 1;
}
}
}
// initialize to global array
dp = DP;
}
// Function to find the minimum of three
static int min(int a, int b, int c)
{
int z = Math.Min(a, b);
return Math.Min(z, c);
}
// Driver Code
public static void Main(String[] args)
{
String s1 = "abcdef";
String s2 = "axcdfdh";
// calculate the DP matrix
editDP(s1, s2);
// print the steps
printChanges(s1, s2);
}
}
// This code is contributed by PrinciRaj1992
change f to h change e to d Add f change b to x
Enfoque para imprimir todas las formas posibles:
Cree una colección de strings que almacenará las operaciones requeridas. Esta colección puede ser un vector de strings en C++ o una lista de strings en Java. Agregue operaciones como imprimirlas antes a esta colección. Luego cree una colección de estas colecciones que almacenará los métodos múltiples (conjuntos de operaciones de string).
Else-if se usó anteriormente para verificar de dónde derivamos el DP[i][j]. Ahora, verifique todos los If para ver si hay más de 1 forma de obtener el elemento. Si la hubo, creamos una nueva colección desde antes, eliminamos la última operación, agregamos esta nueva operación e iniciamos otra instancia de esta función con esta nueva lista. De esta manera, agregue nuevas listas cada vez que haya un nuevo método para cambiar str1 a str2, obteniendo un nuevo método cada vez.
Al llegar al final de cualquiera de las strings, agregue esta lista a la colección de listas, completando así el conjunto de todas las operaciones posibles y agréguelas.
A continuación se muestra la implementación del enfoque anterior:
Java
// Java program to print all the possible
// steps to change a string to another
import java.util.ArrayList;
public class Edit_Distance {
static int dp[][];
// create List of lists that will store all sets of operations
static ArrayList<ArrayList<String> > arrs =
new ArrayList<ArrayList<String> >();
// Function to print all ways
static void printAllChanges(String s1,
String s2, ArrayList<String> changes)
{
int i = s1.length();
int j = s2.length();
// Iterate till end
while (true) {
if (i == 0 || j == 0) {
// Add this list to our List of lists.
arrs.add(changes);
break;
}
// If same
if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
i--;
j--;
}
else {
boolean if1 = false, if2 = false;
// Replace
if (dp[i][j] == dp[i - 1][j - 1] + 1) {
// Add this step
changes.add("Change " + s1.charAt(i - 1)
+ " to " + s2.charAt(j - 1));
i--;
j--;
// note whether this 'if' was true.
if1 = true;
}
// Delete
if (dp[i][j] == dp[i - 1][j] + 1) {
if (if1 == false) {
changes.add("Delete " + s1.charAt(i - 1));
i--;
}
else {
// If the previous method was true,
// create a new list as a copy of previous.
ArrayList<String> changes2 = new ArrayList<String>();
changes2.addAll(changes);
// Remove last operation
changes2.remove(changes.size() - 1);
// Add this new operation
changes2.add("Delete " + s1.charAt(i));
// initiate new new instance of this
// function with remaining substrings
printAllChanges(s1.substring(0, i),
s2.substring(0, j + 1), changes2);
}
if2 = true;
}
// Add character step
if (dp[i][j] == dp[i][j - 1] + 1) {
if (if1 == false && if2 == false) {
changes.add("Add " + s2.charAt(j - 1));
j--;
}
else {
// Add steps
ArrayList<String> changes2 = new ArrayList<String>();
changes2.addAll(changes);
changes2.remove(changes.size() - 1);
changes2.add("Add " + s2.charAt(j));
// Recursively call for the next steps
printAllChanges(s1.substring(0, i + 1),
s2.substring(0, j), changes2);
}
}
}
}
}
// Function to compute the DP matrix
static void editDP(String s1, String s2)
{
int l1 = s1.length();
int l2 = s2.length();
int[][] DP = new int[l1 + 1][l2 + 1];
// initialize by the maximum edits possible
for (int i = 0; i <= l1; i++)
DP[i][0] = i;
for (int j = 0; j <= l2; j++)
DP[0][j] = j;
// Compute the DP matrix
for (int i = 1; i <= l1; i++) {
for (int j = 1; j <= l2; j++) {
// if the characters are same
// no changes required
if (s1.charAt(i - 1) == s2.charAt(j - 1))
DP[i][j] = DP[i - 1][j - 1];
else {
// minimum of three operations possible
DP[i][j] = min(DP[i - 1][j - 1],
DP[i - 1][j], DP[i][j - 1])
+ 1;
}
}
}
// initialize to global array
dp = DP;
}
// Function to find the minimum of three
static int min(int a, int b, int c)
{
int z = Math.min(a, b);
return Math.min(z, c);
}
static void printWays(String s1, String s2,
ArrayList<String> changes)
{
// Function to print all the ways
printAllChanges(s1, s2, new ArrayList<String>());
int i = 1;
// print all the possible ways
for (ArrayList<String> ar : arrs) {
System.out.println("\nMethod " + i++ + " : \n");
for (String s : ar) {
System.out.println(s);
}
}
}
// Driver Code
public static void main(String[] args) throws Exception
{
String s1 = "abcdef";
String s2 = "axcdfdh";
// calculate the DP matrix
editDP(s1, s2);
// Function to print all ways
printWays(s1, s2, new ArrayList<String>());
}
}
Method 1 : Add h Change f to d Change e to f Change b to x Method 2 : Change f to h Add d Change e to f Change b to x Method 3 : Change f to h Change e to d Add f Change b to x
Publicación traducida automáticamente
Artículo escrito por Akarsh Rastogi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA