logo

TechCodeview

Programa Java per comprovar si una cadena és un Palíndrom

Es diu que una corda és un palíndrom si és el mateix si la comencem a llegir d'esquerra a dreta o de dreta a esquerra. En aquest article, aprendrem a comprovar si una cadena és un palíndrom a Java.

Per tant, considerem una cadena str , ara la tasca és esbrinar amb la seva cadena inversa és la mateixa que és.



Exemple de palíndrom:

Entrada: str = abba
Sortida: Sí

Entrada: str = frikis
Sortida: No

Mètodes per a la cadena de palíndrom a Java

Hi ha tres mètodes principals per comprovar el palíndrom de cadenes a Java, tal com s'esmenta a continuació:



importació formiga
  1. Mètode ingenu
  2. Mètode de dos punters
  3. Mètode recursiu
  4. Utilitzant el StringBuilder

1. Enfocament ingenu per comprovar la cadena de palíndrom a Java

Invertint la cadena donada i comparant. Podem comprovar si la cadena donada és un palíndrom comparant la cadena original amb la seva versió invertida.

A continuació es mostra la implementació de l'enfocament anterior:

Java 
// Java Program to implement // Basic Approach to check if // string is a Palindrome import java.io.*; // Driver Class class GFG { // main function public static boolean isPalindrome(String str) { // Initializing an empty string to store the reverse // of the original str String rev = ''; // Initializing a new boolean variable for the // answer boolean ans = false; for (int i = str.length() - 1; i>= 0; i--) { rev = rev + str.charAt(i); } // Comprovant si les dues cadenes són iguals if (str.equals(rev)) { ans = true; } retorn ans; } public static void main(String[] args) { // Cadena d'entrada String str = 'geeks'; // Converteix la cadena en minúscules str = str.toLowerCase(); booleà A = isPalindrom(str); System.out.println(A); } }>>>  
  Sortida  
false>
  
La complexitat del mètode anterior:
 
    Complexitat temporal:    La complexitat temporal del codi donat és O(n), on n és la longitud de la cadena d'entrada. Això es deu al fet que el bucle for itera cada caràcter de la cadena una vegada per crear la cadena inversa.
 
 

entitat relacional

 
    Complexitat espacial:    La complexitat espacial del codi és O(n), on n és la longitud de la cadena d'entrada. Això es deu al fet que la cadena inversa es crea i s'emmagatzema en una variable de cadena independent, que ocupa espai a la memòria proporcional a la longitud de la cadena d'entrada. A més, les altres variables utilitzades al codi (i, str i ans) ocupen una quantitat constant d'espai que és independent de la mida d'entrada.
 
En l'exemple anterior, si escrivim    ABba    en lloc de    abba    , llavors també hauríem d'obtenir la sortida com    sí    . Per tant, hem de canviar el cas de la cadena a minúscules o majúscules abans de comprovar si hi ha un palíndrom. Si no ho fem, obtindrem resultats inesperats. Això es deu al fet que el compilador verifica els caràcters en funció dels seus    ASCII    valor i el    ASCII    el valor de    A    no és el mateix que    a    .
 
    2. Aproximació de dos punters per a P    Programa alindrome en Java
El nostre enfocament serà que primer convertirem la cadena a minúscules. Aleshores, prendrem dues indicacions    i    assenyalant l'inici de la corda i    j    assenyalant el final de la corda. Continua augmentant    i    i decreixent    j    mentre    i     i a cada pas comproveu si els caràcters d'aquests punters són iguals o no. Si no és així, la corda no és un palíndrom, sinó que ho és. 
  
    Exemple 1:    
Java 
// Java program to check whether a // string is a Palindrome // Using two pointing variables // Main class public class GFG { // Method // Returning true if string is palindrome static boolean isPalindrome(String str) { // Pointers pointing to the beginning // and the end of the string int i = 0, j = str.length() - 1; // While there are characters to compare while (i < j) { // If there is a mismatch if (str.charAt(i) != str.charAt(j)) return false; // Increment first pointer and // decrement the other i++; j--; } // Given string is a palindrome return true; } // Method 2 // main driver method public static void main(String[] args) { // Input string String str = 'geeks'; // Convert the string to lowercase str = str.toLowerCase(); // passing bool function till holding true if (isPalindrome(str)) // It is a palindrome System.out.print('Yes'); else // Not a palindrome System.out.print('No'); } }>
   
  Sortida      Complexitat temporal:    La complexitat temporal del codi donat és O(n), on n és la longitud de la cadena d'entrada. Això es deu al fet que el bucle while itera per la meitat de la cadena per comprovar si és un palíndrom. Com que només comprovem la meitat de la cadena, el nombre d'iteracions és proporcional a n/2, que és O(n).
 
    Complexitat espacial:    La complexitat espacial del codi és O(1), perquè el codi només utilitza una quantitat constant d'espai addicional que és independent de la mida d'entrada. Les úniques variables utilitzades al codi són i, j i str, que ocupen una quantitat d'espai constant. No es crea cap espai addicional al codi.
 
    Exemple 2:    
farciment css

Java 
// Java Program to check Whether // the String is Palindrome // or Not // Main class class GFG { // Method 1 // Returns true if string is a palindrome static boolean isPalindrome(String str) { // Pointers pointing to the beginning // and the end of the string int i = 0, j = str.length() - 1; // While there are characters to compare while (i < j) { // If there is a mismatch if (str.charAt(i) != str.charAt(j)) return false; // Increment first pointer and // decrement the other i++; j--; } // Given string is a palindrome return true; } // Main driver method public static void main(String[] args) { String str = 'geeks'; String str2 = 'RACEcar'; // Change strings to lowercase str = str.toLowerCase(); str2 = str2.toLowerCase(); // For string 1 System.out.print('String 1 :'); if (isPalindrome(str)) System.out.print('It is a palindrome'); else System.out.print('It is not a palindrome'); // new line for better readability System.out.println(); // For string 2 System.out.print('String 2 :'); if (isPalindrome(str2)) System.out.print('It is a palindrome'); else System.out.print('It is not a palindrome'); } }>
   
  Sortida  
String 1 :It is not a palindrome String 2 :It is a palindrome>
 
La complexitat del mètode anterior:
 
    Complexitat temporal:    La complexitat temporal del codi donat és O(n), on n és la longitud de la cadena d'entrada. Això es deu al fet que el bucle while del mètode 'isPalindrome' itera per la meitat de la cadena per comprovar si és un palíndrom. Com que només comprovem la meitat de la cadena, el nombre d'iteracions és proporcional a n/2, que és O(n).
 
    Complexitat espacial:    La complexitat espacial del codi és O(1), perquè el codi només utilitza una quantitat constant d'espai addicional que és independent de la mida d'entrada. Les úniques variables que s'utilitzen al codi són i, j, str i str2, que ocupen una quantitat d'espai constant. No es crea cap espai addicional al codi.
dibuix de rectangle gimp

 
    3. Enfocament recursiu per a P    Programa alindrome en Java
L'enfocament és molt senzill. Igual que l'enfocament de dos punters, comprovarem el primer i l'últim valor de la cadena, però aquesta vegada serà mitjançant recursivitat.
 
  • Prenem dos punters i apuntant al començament de la cadena i j apuntant al final de la cadena.
  • Continueu augmentant i i disminuint j mentre i
  • Comproveu si els caràcters d'aquests punters són iguals o no. Ho fem mitjançant recursivitat - (i+1, j-1
  • Si tots els caràcters són iguals als índexs i-iè i jè fins que la condició i>=j es compleix, imprimiu true o false.
    A continuació es mostra la implementació de l'enfocament anterior:    
Java 
// Java program to check whether a // string is a Palindrome using recursion import java.io.*; // Driver Class class GFG { public static boolean isPalindrome(int i, int j, String A) { // comparing the two pointers if (i>= j) { retorna cert; } // comparant els caràcters d'aquests punters if (A.charAt(i) != A.charAt(j)) { return false; } // comprovant tot de nou de manera recursiva retorna isPalindrome(i + 1, j - 1, A); } public static boolean isPalindrome(String A) { return isPalindrome(0, A.length() - 1, A); } // funció principal public static void main(String[] args) { // Introdueix cadena String A = 'geeks'; // Converteix la cadena en minúscules A = A.toLowerCase(); str booleà = isPalindrom(A); System.out.println(str); } }>>>  
  Sortida  
false>
  
La complexitat del mètode anterior:
 
    Complexitat temporal:    La complexitat temporal del codi donat és O(n), on n és la longitud de la cadena d'entrada. Això es deu al fet que la funció `isPalindrome` s'anomena recursivament per als caràcters a les posicions (i+1, j-1) fins que els punters i i j es creuen o els caràcters dels punters no són iguals. Com que comparem cada caràcter de la cadena exactament una vegada, la complexitat temporal és O(n).
 
    Complexitat espacial:    La complexitat espacial del codi és O(n), on n és la longitud de la cadena d'entrada. Això es deu al fet que cada trucada recursiva crea un nou marc de pila que emmagatzema els valors actuals dels paràmetres de la funció i les variables locals. En el pitjor dels casos, la pila de trucades de funció pot créixer fins a n/2 (quan la cadena d'entrada és un palíndrom), de manera que la complexitat de l'espai és O(n).
pagar amb git

 
4. Ús de StringBuilder Approach a Java
En aquest plantejament,
 
  • Primer, prenem l'entrada String de l'usuari.
  • A continuació, creem l'objecte Stringbuilder str1″i hi emmagatzemem el valor de String.
  • El mètode reverse() de Stringbuider ens dóna la cadena inversa. Ee emmagatzema la cadena inversa a str1.
  • Amb l'ajuda del mètode equals() comparem els valors de la cadena, amb l'ajuda de la condició if i else comproveu que el valor de la cadena sigui similar o no.
A continuació es mostra la implementació de l'enfocament anterior:
Java 
import java.util.Scanner; public class Main { public static void main(String[] args) { String str = 'GeeksForGeeks'; // String for testing StringBuilder str1 = new StringBuilder(str); str1.reverse(); if (str.equals(str1.toString())) { System.out.println('Palindrome String'); } else { System.out.println('Not a palindrome String'); } } }>
   
  Sortida      La complexitat del codi anterior:    
  
    Complexitat temporal:    La complexitat temporal del codi és O(n), on n és de nou la longitud de la cadena d'entrada str. El factor principal que contribueix a aquesta complexitat temporal és la inversió de la cadena utilitzant str1.reverse(). Invertir una cadena d'aquesta manera té una complexitat temporal de O(n), on n és la longitud de la cadena. Altres operacions del codi, com ara llegir l'entrada i comparar les cadenes, són operacions de temps constant i no afecten significativament la complexitat del temps global.
 
    Complexitat espacial:    La complexitat espacial del codi Java donat és O(n), on n és la longitud de la cadena d'entrada str. Això es deu al fet que el codi utilitza un StringBuilder per emmagatzemar una còpia invertida de la cadena d'entrada i l'espai necessari per al StringBuilder és proporcional a la longitud de la cadena d'entrada.
 
Referència
 
Per saber més sobre Palíndrom consulteu Programa per a Palíndrom de Cordes .