Java

may 30 2010

Palíndromos en Java

Un palíndromo es una palabra, número o frase que se lee igual de izquierda a derecha o de derecha a izquierda. Un ejemplo clásico es “Dábale arroz a la zorra el abad”, o como dijeron en los Simpson “Anita lava la tina”. También palabras como “ala” o números como “2002″.

Lo que este código hace es leer una línea y ver si ordenándola de alguna manera se puede generar un palíndromo, por ejemplo “Yoga hoy yo hago” NO es un palíndromo, pero si lo ordenamos de esta forma “Yo hago yoga hoy” obtenemos una frase que SI es un palíndromo. Para hacer esto me resultó útil parte del código que publiqué en el post “Anagramas en Java” ya que lo que hago es probar todas las conjugaciones que se pueden hacer con las palabras de la frase ingresada y luego ver si alguna(s) de ellas es un palíndromo.

Es una solución que usa fuerza bruta y se puede mejorar fácilmente, por ejemplo detectando si para la primera palabra de una conjugación hay otra palabra que acabe con la misma letra (“Sx xxxx xx xx xx xxs”) y no hacer conjugaciones en vano, pero esa es otra historia.

Este código lee un número n de casos y luego imprime los parónimos que se pueden obtener ordenando las palabras de alguna manera. Para evitar palíndromos repetidos (por ejemplo si ponemos “a a b” podríamos tener 2 veces “a b a” – “a b a”) seguí la recomendación de Pedro en “Anagramas en Java” y almacené todos los palídromos en un Set y así evitamos los repetidos =D. Si no hay ningún palíndromo posible se muestra el mensaje “imposible”.

PD: El código no funciona con tildes (bienvenido el que quiera agregar los replace() ).

import java.io.*;
import java.util.HashSet;

public class Palindromos {
    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new
        InputStreamReader(System.in));
        System.out.println("Ingrese el numero de lineas:");
        int nro= Integer.parseInt(br.readLine());
        for (int i=0;i<nro;i++){
            String cadena=br.readLine();
            //Pasamos todas las letras a mayuscula para no hacer distincion
            cadena=cadena.toUpperCase();
            //Un arreglo con cada palabra
            String[] palabras=cadena.split(" ");
            //Una variable de control para el método recursivo
            //que se va a usar
            int veces=0;
            //Un arreglo de cadenas que se usará para
            //hacer conjugaciones
            String[] conjugacion= new String[palabras.length];
            //Un Set donde se almacenarán las conjugaciones
            //y permitirá identificar repetidos
            HashSet<String> palindromos=new HashSet<String>();
            //El méttodo recursivo
            conjugar(palabras, veces,conjugacion,palindromos);
            //Output
            if (palindromos.isEmpty()){
                System.out.println("imposible");
            }else{
                System.out.println("Palindromos encontrados: ");
                for(String pal:palindromos){
                    System.out.println("- "+pal);
                }
            }
        }
    }

    public static void conjugar(String[] palabras, int veces,
            String[] conjugacion, HashSet<String> palindromos){
        //Si la conjugacion está completa, probamos si es palíndromo
        if (veces==palabras.length){
            probarPalindromo(conjugacion,palindromos);
            return;
        }
        //Desde aquí es casi idéntico que el código del anagrama
        veces++;
        for (int i=0; i<=palabras.length-1;i++){
            if (palabras[i].compareTo("@")==0){
                continue;
            }else{
                String palabraAuxiliar=palabras[i];
                conjugacion[veces-1]=palabraAuxiliar;
                palabras[i]="@";
                conjugar(palabras,veces,conjugacion,palindromos);
                palabras[i]=palabraAuxiliar;
            }
        }
    }

    public static void probarPalindromo(String[] conjugacion,
            HashSet<String> palindromos){
        //Armamos una cadena en base al arreglo de Strings
        //La cadena no tendrá espacios entre letras,
        //ya que para ser palíndromo
        //estas no se toman en cuenta
        String cadena1="";
        for (String s:conjugacion){
            cadena1=cadena1+s;
        }
        int veces;
        //Luego lo pasamos a un arreglo de caracteres
        //para hacer las comparaciones
        //Esto se puede hacer de varias maneras
        char[] carac=cadena1.toCharArray();
        int longitud=carac.length;
        if (longitud % 2==0){
            veces=longitud/2;
        }else{
            veces=(longitud-1)/2;
        }
        //Una bandera que indica que no es palindromo
        boolean flagNoPalindromo=false;
        for(int i=0;i<=veces;i++){
            //La idea es comparar el primer caracter con el último
            //Luego el segundo con el penúltimo, etc etc
            if (carac[i]==carac[longitud-i-1]){
            }else{
                flagNoPalindromo=true;
            }
        }
        if (flagNoPalindromo==true){
            return;
        }
        //Armamos otra cadena, ahora los espacios entre letras
        String cadenaSalida="";
        for (String s:conjugacion){
            cadenaSalida=cadenaSalida+s+" ";
        }
        //Finalmente le damos un poco de formato y lo agregamos al Set
        String cadenaFormateada=cadenaSalida.substring(0,1)+
                cadenaSalida.substring(1,
                cadenaSalida.length()-1).toLowerCase();
        cadenaFormateada="\""+ cadenaFormateada+"\"";
        palindromos.add(cadenaFormateada);
    }
}

By Diego • Java • 0 • Tags: codigo fuente, palindromo