Compruebe la cuerda para palíndromo

93

Un palíndromo es una palabra, frase, número u otra secuencia de unidades que se puede leer de la misma manera en cualquier dirección.

Para comprobar si una palabra es un palíndromo, obtengo la matriz de caracteres de la palabra y comparo los caracteres. Lo probé y parece funcionar. Sin embargo quiero saber si está bien o si hay algo que mejorar.

Aquí está mi código:

public class Aufg1 {
    public static void main(String[] args) {
        String wort = "reliefpfpfeiller";
        char[] warray = wort.toCharArray(); 
        System.out.println(istPalindrom(warray));       
    }

    public static boolean istPalindrom(char[] wort){
        boolean palindrom = false;
        if(wort.length%2 == 0){
            for(int i = 0; i < wort.length/2-1; i++){
                if(wort[i] != wort[wort.length-i-1]){
                    return false;
                }else{
                    palindrom = true;
                }
            }
        }else{
            for(int i = 0; i < (wort.length-1)/2-1; i++){
                if(wort[i] != wort[wort.length-i-1]){
                    return false;
                }else{
                    palindrom = true;
                }
            }
        }
        return palindrom;
    }
}
Voto a favor
fuente
4
No estoy seguro si esto es intencional, pero la cadena en su ejemplo - reliefpfpfeiller - no es un palíndromo
barrowc

Respuestas:

185

Por qué no solo:

public static boolean istPalindrom(char[] word){
    int i1 = 0;
    int i2 = word.length - 1;
    while (i2 > i1) {
        if (word[i1] != word[i2]) {
            return false;
        }
        ++i1;
        --i2;
    }
    return true;
}

Ejemplo:

La entrada es "andna".
i1 será 0 e i2 será 4.

Primera iteración de bucle que compararemos word[0]y word[4]. Son iguales, así que incrementamos i1 (ahora es 1) y disminuimos i2 (ahora es 3).
Entonces comparamos las n. Son iguales, así que incrementamos i1 (ahora es 2) y disminuimos i2 (es 2).
Ahora i1 e i2 son iguales (ambos son 2), por lo que la condición para el ciclo while ya no es verdadera, por lo que el ciclo termina y devolvemos verdadero.

dcp
fuente
1
en lugar de preincremento (++ i1 y --i2), también podemos usar post incremento (i1 ++, i2 -) ¡el resultado es el mismo, creo!
user0946076422
@ user0946076422 Sí. Yo también me sentí así. Sería genial si OP tiene una explicación diferente.
Vijay Tholpadi
3
@Vijay Tholpadi: es una preferencia de codificación más que cualquier otra cosa. El incremento posterior lograría el mismo resultado en este ejemplo en particular, pero siempre uso el incremento previo a menos que haya una razón específica para no hacerlo.
DCP
118

Puede comprobar si una cuerda es un palíndromo comparándola con el reverso de sí misma:

public static boolean isPalindrome(String str) {
    return str.equals(new StringBuilder(str).reverse().toString());
}

o para versiones de Java anteriores a la 1.5,

public static boolean isPalindrome(String str) {
    return str.equals(new StringBuffer().append(str).reverse().toString());
}

EDITAR: @FernandoPelliccioni proporcionó un análisis muy completo de la eficiencia (o falta de ella) de esta solución, tanto en términos de tiempo como de espacio. Si está interesado en la complejidad computacional de esta y otras posibles soluciones a esta pregunta, ¡léala!

Greg
fuente
10
Compare la complejidad de su algoritmo con respecto a otros.
Fernando Pelliccioni
2
@FernandoPelliccioni, creo que es la misma complejidad que las otras soluciones, ¿no?
aioobe
1
@Fernando, por lo que puedo decir, todas las respuestas tienen una complejidad lineal. Debido a esto, no hay forma de dar una respuesta definitiva sobre qué solución es más eficiente. Puede ejecutar evaluaciones comparativas, pero serían específicas para una JVM y JRE en particular. Mucha suerte con la publicación de tu blog. Estoy deseando leerlo.
aioobe
1
@FernandoPelliccioni Es un modismo para alguien inteligente, inteligente, capaz de encontrar soluciones a situaciones difíciles. :-)
Sipty
1
@FernandoPelliccioni buen análisis
Saravana
66

Una versión concisa, que no implica (de manera ineficiente) inicializar un montón de objetos:

boolean isPalindrome(String str) {    
    int n = str.length();
    for( int i = 0; i < n/2; i++ )
        if (str.charAt(i) != str.charAt(n-i-1)) return false;
    return true;    
}
Andrew Mao
fuente
18

Alternativamente, recursividad .

Para cualquiera que esté buscando una solución recursiva más corta, para verificar si una cadena dada satisface como palíndromo:

private boolean isPalindrome(String s) {
    int length = s.length();

    if (length < 2) // If the string only has 1 char or is empty
        return true;
    else {
        // Check opposite ends of the string for equality
        if (s.charAt(0) != s.charAt(length - 1))
            return false;
        // Function call for string with the two ends snipped off
        else
            return isPalindrome(s.substring(1, length - 1));
    }
}

O incluso más corto , si lo desea:

private boolean isPalindrome(String s) {
    int length = s.length();
    if (length < 2) return true;
    return s.charAt(0) != s.charAt(length - 1) ? false :
            isPalindrome(s.substring(1, length - 1));
}
Keith OYS
fuente
3
Buen código, la recursividad lo hace realmente fácil y con menos líneas en el código.
Akash5288
2
la versión más corta se puede simplificar:return s.charAt(0) == s.charAt(l - 1) && isPalindrome(s.substring(1, l - 1));
bóveda
10

Vaya, Java:

public boolean isPalindrome (String word) {
    String myWord = word.replaceAll("\\s+","");
    String reverse = new StringBuffer(myWord).reverse().toString();
    return reverse.equalsIgnoreCase(myWord);
}

isPalindrome("Never Odd or Even"); // True
isPalindrome("Never Odd or Even1"); // False
Francisco Gutiérrez
fuente
Éstas me parecieron la solución más sencilla y directa. ¡Gracias!
RShome
4

también una solución de aspecto diferente:

public static boolean isPalindrome(String s) {

        for (int i=0 , j=s.length()-1 ; i<j ; i++ , j-- ) {

            if ( s.charAt(i) != s.charAt(j) ) {
                return false;
            }
        }

        return true;
    }
Mona Jalal
fuente
4

Y aquí una completa solución de transmisión de Java 8 . Un IntStream proporciona todos los índices hasta la mitad de la longitud de las cadenas y luego se realiza una comparación desde el principio y desde el final.

public static void main(String[] args) {
    for (String testStr : Arrays.asList("testset", "none", "andna", "haah", "habh", "haaah")) {
        System.out.println("testing " + testStr + " is palindrome=" + isPalindrome(testStr));
    }
}

public static boolean isPalindrome(String str) {
    return IntStream.range(0, str.length() / 2)
            .noneMatch(i -> str.charAt(i) != str.charAt(str.length() - i - 1));
}

La salida es:

testing testset is palindrome=true
testing none is palindrome=false
testing andna is palindrome=true
testing haah is palindrome=true
testing habh is palindrome=false
testing haaah is palindrome=true
wumpz
fuente
1
¿Por qué no allMatchcon allMatch(i -> str.charAt(i) == str.charAt(str.length() - i - 1))?
gil.fernandes
4
public class Palindromes {
    public static void main(String[] args) {
         String word = "reliefpfpfeiller";
         char[] warray = word.toCharArray(); 
         System.out.println(isPalindrome(warray));       
    }

    public static boolean isPalindrome(char[] word){
        if(word.length%2 == 0){
            for(int i = 0; i < word.length/2-1; i++){
                if(word[i] != word[word.length-i-1]){
                    return false;
                }
            }
        }else{
            for(int i = 0; i < (word.length-1)/2-1; i++){
                if(word[i] != word[word.length-i-1]){
                    return false;
                }
            }
        }
        return true;
    }
}
Casey
fuente
2
simplificado un poco. ¡pero me gusta la respuesta de dcp!
Casey
¿Has intentado correr isPalindrome()con "cbb"?
kenshinji
3
public class palindrome {
public static void main(String[] args) {
    StringBuffer strBuf1 = new StringBuffer("malayalam");
    StringBuffer strBuf2 = new StringBuffer("malayalam");
    strBuf2.reverse();


    System.out.println(strBuf2);
    System.out.println((strBuf1.toString()).equals(strBuf2.toString()));
    if ((strBuf1.toString()).equals(strBuf2.toString()))
        System.out.println("palindrome");
    else
        System.out.println("not a palindrome");
}

}

usuario2039532
fuente
3

Trabajé en una solución para una pregunta que estaba marcada como duplicada de esta. Bien podría tirarlo aquí ...

La pregunta solicitó una sola línea para resolver esto, y la tomé más como el palíndromo literario, por lo que los espacios, la puntuación y las mayúsculas / minúsculas pueden alterar el resultado.

Aquí está la fea solución con una pequeña clase de prueba:

public class Palindrome {
   public static boolean isPalendrome(String arg) {
         return arg.replaceAll("[^A-Za-z]", "").equalsIgnoreCase(new StringBuilder(arg).reverse().toString().replaceAll("[^A-Za-z]", ""));
   }
   public static void main(String[] args) {
      System.out.println(isPalendrome("hiya"));
      System.out.println(isPalendrome("star buttons not tub rats"));
      System.out.println(isPalendrome("stab nail at ill Italian bats!"));
      return;
   }
}

Lamento que sea un poco desagradable, pero la otra pregunta especificó una sola línea.

Bagazo
fuente
1
Solo curiosidad, ¿por qué el operador ternario al final?
typingduck
Absolutamente nada, no debí haber tomado mi café. Arreglaré mi respuesta - ¡gracias !.
Marc
3

Verificando palíndromo para la primera mitad de la cadena con el resto, este caso asume la eliminación de cualquier espacio en blanco.

public int isPalindrome(String a) {
        //Remove all spaces and non alpha characters
        String ab = a.replaceAll("[^A-Za-z0-9]", "").toLowerCase();
        //System.out.println(ab);

        for (int i=0; i<ab.length()/2; i++) {
            if(ab.charAt(i) != ab.charAt((ab.length()-1)-i)) {
                return 0;
            }
        }   
        return 1;
    }
Abhilash Muthuraj
fuente
2

Soy nuevo en Java y acepto su pregunta como un desafío para mejorar mis conocimientos.

import java.util.ArrayList;
import java.util.List;

public class PalindromeRecursiveBoolean {

    public static boolean isPalindrome(String str) {

        str = str.toUpperCase();
        char[] strChars = str.toCharArray();

        List<Character> word = new ArrayList<>();
        for (char c : strChars) {
            word.add(c);
        }

        while (true) {
            if ((word.size() == 1) || (word.size() == 0)) {
                return true;
            }
            if (word.get(0) == word.get(word.size() - 1)) {
                word.remove(0);
                word.remove(word.size() - 1);
            } else {
                return false;

            }

        }
    }
}
  1. Si la cuerda no tiene letras o solo tiene una letra, es un palíndromo.
  2. De lo contrario, compare la primera y la última letra de la cadena.
    • Si la primera y la última letra difieren, entonces la cuerda no es un palíndromo
    • De lo contrario, la primera y la última letra son iguales. Quítelos de la cuerda y determine si la cuerda que queda es un palíndromo. Tome la respuesta para esta cadena más pequeña y úsela como la respuesta para la cadena original, luego repita desde 1 .
gogobebe2
fuente
1

Probar esto :

import java.util.*;
    public class str {

        public static void main(String args[])
        {
          Scanner in=new Scanner(System.in);
          System.out.println("ENTER YOUR STRING: ");
          String a=in.nextLine();
          System.out.println("GIVEN STRING IS: "+a);
          StringBuffer str=new StringBuffer(a);
          StringBuffer str2=new StringBuffer(str.reverse());
          String s2=new String(str2);
          System.out.println("THE REVERSED STRING IS: "+str2);
            if(a.equals(s2))    
                System.out.println("ITS A PALINDROME");
            else
                System.out.println("ITS NOT A PALINDROME");
            }
    }
ARAVIN
fuente
1
public boolean isPalindrome(String abc){
    if(abc != null && abc.length() > 0){
        char[] arr = abc.toCharArray();
        for (int i = 0; i < arr.length/2; i++) {
            if(arr[i] != arr[arr.length - 1 - i]){
                return false;
            }
        }
        return true;
    }
    return false;
}
Amandeep Dhanjal
fuente
1

Otra forma es usar char Array

public class Palindrome {

public static void main(String[] args) {
    String str = "madam";
    if(isPalindrome(str)) {
        System.out.println("Palindrome");
    } else {
        System.out.println("Not a Palindrome");
    }
}

private static boolean isPalindrome(String str) {
    // Convert String to char array
    char[] charArray = str.toCharArray();  
    for(int i=0; i < str.length(); i++) {
        if(charArray[i] != charArray[(str.length()-1) - i]) {
            return false;
        }
    }
    return true;
}

}

Madura Harshana
fuente
1
Este enfoque es excelente. Complejidad temporal O (n), Complejidad espacial O (1)
kanaparthikiran
1

Aquí mi análisis de la respuesta de @Greg: componentsprogramming.com/palindromes


Nota al margen: Pero, para mí, es importante hacerlo de forma genérica . Los requisitos son que la secuencia sea iterable bidireccionalmente y que los elementos de la secuencia sean comparables utilizando la igualdad. No sé cómo hacerlo en Java, pero aquí hay una versión de C ++, no conozco una mejor manera de hacerlo para secuencias bidireccionales.

template <BidirectionalIterator I> 
    requires( EqualityComparable< ValueType<I> > ) 
bool palindrome( I first, I last ) 
{ 
    I m = middle(first, last); 
    auto rfirst = boost::make_reverse_iterator(last); 
    return std::equal(first, m, rfirst); 
} 

Complejidad: tiempo lineal,

  • Si I es RandomAccessIterator: piso (n / 2) comparaciones y piso (n / 2) * 2 iteraciones

  • Si I es BidirectionalIterator: comparaciones de piso (n / 2) y piso (n / 2) * 2 iteraciones más (3/2) * n iteraciones para encontrar el medio (función del medio)

  • almacenamiento: O (1)

  • Sin memoria asignada dinámica


Fernando Pelliccioni
fuente
1

Recientemente escribí un programa palindrome que no usa StringBuilder. Una respuesta tardía, pero esto puede resultar útil para algunas personas.

public boolean isPalindrome(String value) {
    boolean isPalindrome = true;
    for (int i = 0 , j = value.length() - 1 ; i < j ; i ++ , j --) {
        if (value.charAt(i) != value.charAt(j)) {
            isPalindrome = false;
        }
    }
    return isPalindrome;
}
capt.swag
fuente
1

Usando la pila, se puede hacer así

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
import java.util.*;

public class Solution {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String str=in.nextLine();
        str.replaceAll("\\s+","");
        //System.out.println(str);
        Stack<String> stack=new Stack<String>();
        stack.push(str);
        String str_rev=stack.pop();
        if(str.equals(str_rev)){
            System.out.println("Palindrome"); 
        }else{
             System.out.println("Not Palindrome");
        }
    }
}
aayushi
fuente
como debe saberlo, la pila es de tipo LIFO, lo que significa que básicamente está empujando datos al principio de la pila y recuperando datos del final de la pila usando pop (). ¡Espero que esto ayude!
aayushi
1
 public static boolean isPalindrome(String word) {
    String str = "";
    for (int i=word.length()-1; i>=0;  i--){
        str = str + word.charAt(i);
    }
   if(str.equalsIgnoreCase(word)){
       return true;
   }else{
       return false;
   }

}
Chandara Chea
fuente
1

¡Increíble cuántas soluciones diferentes para un problema tan simple existen! Aqui hay otro más.

private static boolean palindrome(String s){
    String revS = "";
    String checkS = s.toLowerCase();
    String[] checkSArr = checkS.split("");

    for(String e : checkSArr){
        revS = e + revS;
    }

    return (checkS.equals(revS)) ? true : false;
}
Felix
fuente
1
  • Esta implementación funciona para números y cadenas.
  • Como no estamos escribiendo nada, no es necesario convertir la cadena en la matriz de caracteres.
public static boolean isPalindrome(Object obj)
{
    String s = String.valueOf(obj);

    for(int left=0, right=s.length()-1; left < right; left++,right--)
    {
        if(s.charAt(left++) != s.charAt(right--))
            return false;
    }
    return true;
}
Pratik Patil
fuente
1

Por qué no solo:

boolean isPalindrom(String s) {
        char[] myChars = s.toCharArray();
        for (int i = 0; i < myChars.length/2; i++) {
            if (myChars[i] != myChars[myChars.length - 1 - i]) {
                return false;
            }
        }
        return true;
}
sodomark
fuente
0
import java.util.Scanner;


public class Palindrom {

    public static void main(String []args)
    {
        Scanner in = new Scanner(System.in);
        String str= in.nextLine();
        int x= str.length();

        if(x%2!=0)
        {
            for(int i=0;i<x/2;i++)
            {

                if(str.charAt(i)==str.charAt(x-1-i))
                {
                    continue;
                }
                else 
                {
                    System.out.println("String is not a palindrom");
                    break;
                }
            }
        }
        else
        {
            for(int i=0;i<=x/2;i++)
            {
                if(str.charAt(i)==str.charAt(x-1-i))
                {
                    continue;
                }
                else 
                {
                    System.out.println("String is not a palindrom");
                    break;
                }

            }
        }
    }

}
Nitesh
fuente
0
private static boolean isPalindrome(String word) {

        int z = word.length();
        boolean isPalindrome = false;

        for (int i = 0; i <= word.length() / 2; i++) {
            if (word.charAt(i) == word.charAt(--z)) {
                isPalindrome = true;
            }
        }

        return isPalindrome;
    }
Ángela Sánchez
fuente
0

Estaba buscando una solución que no solo funcionara para palíndromos como ...

  • "Kayac"
  • "Señora"

... pero también para ...

  • "¡Un hombre, un plan, un canal, Panamá!"
  • "¿Fue un coche o un gato lo que vi?"
  • "No hay 'x' en Nixon"

Iterativo : se ha demostrado que es una buena solución.

private boolean isPalindromeIterative(final String string)
    {
        final char[] characters =
            string.replaceAll("[\\W]", "").toLowerCase().toCharArray();

        int iteratorLeft = 0;
        int iteratorEnd = characters.length - 1;

        while (iteratorEnd > iteratorLeft)
        {
            if (characters[iteratorLeft++] != characters[iteratorEnd--])
            {
                return false;
            }
        }

        return true;
    }

Recursivo . Creo que esta solución no debería ser mucho peor que la iterativa. Es un poco cutre, necesitamos extraer el paso de limpieza del método para evitar procesamientos innecesarios.

private boolean isPalindromeRecursive(final String string)
        {
            final String cleanString = string.replaceAll("[\\W]", "").toLowerCase();
            return isPalindromeRecursiveRecursion(cleanString);
        }

private boolean isPalindromeRecursiveRecursion(final String cleanString)
        {
            final int cleanStringLength = cleanString.length();

            return cleanStringLength <= 1 || cleanString.charAt(0) ==
                       cleanString.charAt(cleanStringLength - 1) &&
                       isPalindromeRecursiveRecursion  
                           (cleanString.substring(1, cleanStringLength - 1));
        }

Inversión : se ha demostrado que es una solución cara.

private boolean isPalindromeReversing(final String string)
    {
        final String cleanString = string.replaceAll("[\\W]", "").toLowerCase();
        return cleanString.equals(new StringBuilder(cleanString).reverse().toString());
    }

Todos los créditos para los chicos que respondieron en esta publicación y aclararon el tema.

Sotti
fuente
0

Considerando no letras en las palabras

public static boolean palindromeWords(String s ){

        int left=0;
        int right=s.length()-1;

        while(left<=right){

            while(left<right && !Character.isLetter(s.charAt(left))){
                left++;
            }
            while(right>0 && !Character.isLetter(s.charAt(right))){
                right--;
            }

            if((s.charAt(left++))!=(s.charAt(right--))){
                return false;
            }
        }
        return true;
    }

———

@Test
public void testPalindromeWords(){
    assertTrue(StringExercise.palindromeWords("ece"));
    assertTrue(StringExercise.palindromeWords("kavak"));
    assertFalse(StringExercise.palindromeWords("kavakdf"));
    assertTrue(StringExercise.palindromeWords("akka"));
    assertTrue(StringExercise.palindromeWords("??e@@c_--e"));
}
huseyin
fuente
0

Aquí puede comprobar palíndromo una serie de cadenas de forma dinámica

import java.util.Scanner;

public class Checkpalindrome {
 public static void main(String args[]) {
  String original, reverse = "";
  Scanner in = new Scanner(System.in);
  System.out.println("Enter How Many number of Input you want : ");
  int numOfInt = in.nextInt();
  original = in.nextLine();
do {
  if (numOfInt == 0) {
    System.out.println("Your Input Conplete");
   } 
  else {
    System.out.println("Enter a string to check palindrome");
    original = in.nextLine();

    StringBuffer buffer = new StringBuffer(original);
    reverse = buffer.reverse().toString();

  if (original.equalsIgnoreCase(reverse)) {
    System.out.println("The entered string is Palindrome:"+reverse);
   } 
  else {
    System.out.println("The entered string is not Palindrome:"+reverse);
    }
 }
   numOfInt--;
    } while (numOfInt >= 0);
}
}
Md. Nasir Uddin
fuente
0

En mi opinión, la forma recursiva es la más simple y clara.

public static boolean isPal(String s)
{   
    if(s.length() == 0 || s.length() == 1)
        return true; 
    if(s.charAt(0) == s.charAt(s.length()-1))
       return isPal(s.substring(1, s.length()-1));                
   return false;
}
John Smith
fuente
2
Esto ya se usó en una respuesta: Verifique la cadena para palíndromo (solo una nota)
Tom
lo siento, me lo perdí.
John Smith
0

aquí, buscando el palíndromo más grande de una cadena, siempre comenzando desde el primer carácter.

public static String largestPalindromeInString(String in) {
    int right = in.length() - 1;
    int left = 0;
    char[] word = in.toCharArray();
    while (right > left && word[right] != word[left]) {
        right--;
    }
    int lenght = right + 1;
    while (right > left && word[right] == word[left]) {

        left++;
        right--;

    }
    if (0 >= right - left) {
        return new String(Arrays.copyOf(word, lenght ));
    } else {
        return largestPalindromeInString(
                new String(Arrays.copyOf(word, in.length() - 1)));
    }
}
juanmf
fuente
0

Fragmento de código:

import java.util.Scanner;

 class main
 {
    public static void main(String []args)
    {
       Scanner sc = new Scanner(System.in);
       String str = sc.next();
       String reverse = new StringBuffer(str).reverse().toString();

        if(str.equals(reverse))
            System.out.println("Pallindrome");
        else
            System.out.println("Not Pallindrome");
     }
}
rashedcs
fuente