Programación dinámica/Problema del cambio de palabra (programación dinámica en Java)

Esta página se ha identificado como una «hoja suelta» de algún wikilibro. Esta hoja se ha marcado con la categoría Wikilibros:Hojas sueltas y se debe integrar al wikilibro correspondiente.

Plantilla:A wikilibros El problema del cambio de palabra se produce cuando siendo "u" y "v" dos palabras (cadenas de caracteres). Se desea transformar u en v con el mínimo número de operaciones básicas del tipo siguiente: eliminar un carácter, añadir un carácter, y cambiar un carácter. Por ejemplo, podemos pasar de abbac a abcbc en tres pasos:

abbac _ abac (eliminamos b en la posición 3)
_ ababc (añadimos b en la posición 4)
_ abcbc (cambiamos a en la posición 3 por c)

Sin embargo, esta tranformación no es óptima. Lo que queremos en este caso es diseñar un algoritmo que calcule el número mínimo de operaciones, de esos tres tipos, necesarias para transformar u en v y cuáles son esas operaciones. En el caso anterior se podría llevar a cabo con dos operaciones nada más:

abbac → abcac (cambiamos b en la posición 3 por c)
→abcbc (cambiamos a en la posición 4 por b)

Código

Este código no está del todo bien, ya que no se contempla el caso en el que las palabras tienen letras iguales, es decir, es más fácil agregar y quitar algunas letras, que cambiarlas todas.

Ejemplo: casa asaa

es mejor agregar una c al comienzo y eliminar la última letra, que cambiar las letras, cosa que haría el código dado al notar que las palabras tienen la misma longitud.

Primera clase

 
import javax.swing.JOptionPane;

public class Aplicacion
{
	public static void main ( String args[])
	{
		CambioPalabra palabras;
		String palabra_u = leerPalabra("Ingrese la palabra U:");
		String palabra_v = leerPalabra ("Ingrese la palabra V:");
		palabras = new CambioPalabra ( palabra_u, palabra_v);
		int des = palabras.verificarPalabras( palabras.getPal1(), palabras.getPal2());
		if ( des == 1)
		{
			JOptionPane.showMessageDialog( null, "para trasformar la palabra U: " +palabra_u +
                                                    ",\n en la palabra V: " + palabra_v + 
                                                    ",\n se necesito de: " + palabras.getContador() + 
                                                    " operaciones.", "RESPUESTA", JOptionPane.PLAIN_MESSAGE);
		}
		
	}
	
	public static String leerPalabra (String mensaje)
	{
		return JOptionPane.showInputDialog(mensaje);
	}
}

Segunda clase

 
public class CambioPalabra 
{
	public char pal1[];
	public char pal2 [];
	char tabla_aux[]; 
	int contador;

	public CambioPalabra ( String u, String v)
	{
		pal1 = u.toCharArray();
		pal2 = v.toCharArray();
		tabla_aux = new char[pal2.length];
		contador =0; 
	}

	public int verificarPalabras ( char[] u, char[]v)
	{
		if ( u.length == v.length)
		{
			tabla_aux = cambiarLetras(u, v);
			return 1;
		}
		else
		{
			if (u.length<v.length)
			{
				tabla_aux = agregarLetra (u,v);
				return 1;
			}
			else
			{
				if ( u.length> v.length)
				{
					tabla_aux= eliminarLetra (u, v);
					return 1;
				}
			}
		}
		return 0;
	}

	public char[] cambiarLetras ( char [] u, char [] v)
	{
		char aux[];
		aux = new char [v.length];
		for ( int i=0; i<u.length; i++)
		{
			if ( u[i]==v[i])
			{
				aux[i]=u[i];
			}
			else
			{
				contador++;
				aux[i]= v[i];
			}
		}
		return aux;
	}
	/**
	 * Este metodo calcula cuantas letra hay que eliminar y luego 
	 * cambiar para convertir u en v
	 * @param u, es la palabra a modificar
	 * @param v, es la palabra a la que hay que llegar
	 * @return, retorna una cadena igual a v
	 */
	public char[] eliminarLetra ( char[]u, char v[])
	{
		char aux[];
		int pos=0;
		aux= new char[v.length];
		for ( int i=0; i<u.length;i++)
		{
			if ( i >= pos)
			{
				if ( pos<v.length)
				{
					if ( u[i]== v[pos])
					{ System.out.println("este codigo no esta 100% terminado");
						aux[pos]= v[pos];
						pos++;
						u[i]='0';
					}	
				}
			}
		}
		contador = (u.length-v.length);
		aux = cambiarLetras(aux, v); 
		return aux;
	}
	public char[] agregarLetra(char[]u, char[] v) 
	{
		char aux[], aux2[];
		aux = new char[v.length];
		int pos =0, cant=0;
		for (int i =0; i<u.length; i++)
		{
			aux[i]= u[i];	
		}
		aux2 = aux;
		for ( int j=0; j<v.length;j++)
		{

			if ( aux[pos]==v[j])
			{
				aux[j]='0';
				aux2[pos]=v[pos];
				pos++;
			}
			else
			{
				cant++;
			}


		}
		if ( cant<(v.length-u.length))
		{
			contador++;
		}
		else
		{

		}
		aux2 = cambiarLetras(aux2, v);
		return aux;
	}

	public char[] getPal1() 
	{
		return pal1;
	}

	public char[] getPal2() 
	{
		return pal2;
	}

	public int getContador()
	{
		return contador;
	}
}

Véase también