Se spune că un șir este un palindrom dacă este același dacă începem să-l citim de la stânga la dreapta sau de la dreapta la stânga. În acest articol, vom învăța cum să verificăm dacă un șir este un palindrom în Java.

Deci, să luăm în considerare un șir str , acum sarcina este doar să afli că șirul său invers este același.

Exemplu de palindrom:

Intrare: str = abba
Ieșire: da

Intrare: str = tocilari
Ieșire: Nu

Metode pentru șirul de palindrom în Java

Există trei metode majore de a verifica palindromul șirurilor în Java, așa cum este menționat mai jos:

1. Metoda naivă
2. Metoda cu două indicatori
3. Metoda recursiva
4. Folosind StringBuilder

1. Abordare naivă pentru a verifica șirul de palindrom în Java

Prin inversarea șirului dat și comparând. Putem verifica dacă șirul dat este un palindrom comparând șirul original cu versiunea sa inversată.

Mai jos este implementarea abordării de mai sus:

// 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); } // Verificați dacă ambele șiruri sunt egale if (str.equals(rev)) { ans = true; } return ans; } public static void main(String[] args) { // Sir de intrare String str = 'geeks'; // Convertiți șirul în minuscule str = str.toLowerCase(); boolean A = isPalindrom(str); System.out.println(A); } }>>>   
  Ieșire   
false 
    
 Complexitatea metodei de mai sus:  
 
 
    Complexitatea timpului:     Complexitatea de timp a codului dat este O(n), unde n este lungimea șirului de intrare. Acest lucru se datorează faptului că bucla for iterează prin fiecare caracter din șir o dată pentru a crea șirul invers.  
  
    Complexitatea spațiului:     Complexitatea spațială a codului este O(n), unde n este lungimea șirului de intrare. Acest lucru se datorează faptului că șirul invers este creat și stocat într-o variabilă șir separată, care ocupă spațiu în memorie proporțional cu lungimea șirului de intrare. În plus, celelalte variabile utilizate în cod (i, str și ans) ocupă o cantitate constantă de spațiu care este independentă de dimensiunea de intrare.  
  
 
 În exemplul de mai sus, dacă scriem     ABba     in locul     abba     , atunci, de asemenea, ar trebui să obținem rezultatul ca     da     . Deci, trebuie să schimbăm majusculele șirului fie cu litere mici, fie cu majuscule înainte de a-l verifica pentru un palindrom. Dacă nu facem acest lucru, vom obține rezultate neașteptate. Acest lucru se datorează faptului că compilatorul verifică caracterele pe baza lor     ASCII     valoarea și cel     ASCII     valoarea     A     nu este la fel ca     A     .  
  
    2. Abordarea cu două puncte pentru P     Programul alindrome în Java  
 
 Abordarea noastră va fi aceea că vom converti mai întâi șirul în minuscule. Apoi, vom lua două indicații     i     arătând spre începutul șirului și     j     arătând spre capătul sforii. Continuați să creșteți     i     si in decrementare     j     in timp ce     i        și la fiecare pas verificați dacă caracterele de la acești indicatori sunt aceleași sau nu. Dacă nu, atunci șirul nu este un palindrom, altfel este.   
   
    Exemplul 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'); } } 
    
  Ieșire       Complexitatea timpului:     Complexitatea de timp a codului dat este O(n), unde n este lungimea șirului de intrare. Acest lucru se datorează faptului că bucla while iterează prin jumătate din șir pentru a verifica dacă este un palindrom. Deoarece verificăm doar jumătate din șir, numărul de iterații este proporțional cu n/2, care este O(n).  
  
    Complexitatea spațiului:     Complexitatea spațială a codului este O(1), deoarece codul folosește doar o cantitate constantă de spațiu suplimentar care este independent de dimensiunea de intrare. Singurele variabile utilizate în cod sunt i, j și str, care ocupă fiecare o cantitate constantă de spațiu. Nu se creează spațiu suplimentar în cod.  
   
    Exemplul 2:     
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'); } } 
    
  Ieșire   
String 1 :It is not a palindrome String 2 :It is a palindrome 
  
 Complexitatea metodei de mai sus:  
 
 
    Complexitatea timpului:     Complexitatea de timp a codului dat este O(n), unde n este lungimea șirului de intrare. Acest lucru se datorează faptului că bucla while din metoda „isPalindrome” iterează prin jumătate din șir pentru a verifica dacă este un palindrom. Deoarece verificăm doar jumătate din șir, numărul de iterații este proporțional cu n/2, care este O(n).  
  
    Complexitatea spațiului:     Complexitatea spațială a codului este O(1), deoarece codul folosește doar o cantitate constantă de spațiu suplimentar care este independent de dimensiunea de intrare. Singurele variabile utilizate în cod sunt i, j, str și str2, care ocupă fiecare o cantitate constantă de spațiu. Nu se creează spațiu suplimentar în cod.  
  
 
    3. Abordare recursiva pentru P     Programul alindrome în Java  
 
 Abordarea este foarte simplă. La fel ca abordarea cu două puncte, vom verifica prima și ultima valoare a șirului, dar de data aceasta va fi prin recursivitate.  
  
 
 Vom lua doi indicatori i care indică începutul șirului și j spre sfârșitul șirului.  
 
 Continuați să creșteți i și să micșorați j în timp ce i    
 
 Verificați dacă caracterele de la aceste indicatoare sunt aceleași sau nu. Facem acest lucru prin recursivitate – (i+1, j-1  
 
 Dacă toate caracterele sunt aceleași pe indexul i-lea și j-lea până când condiția i>=j este satisfăcută, tipăriți true altfel false.  
 
 
    Mai jos este implementarea abordării de mai sus:     
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) { return true; } // compararea caracterelor de pe acele pointeri if (A.charAt(i) != A.charAt(j)) { return false; } // verificând totul din nou recursiv return isPalindrom(i + 1, j - 1, A); } public static boolean isPalindrom(String A) { return isPalindrome(0, A.length() - 1, A); } // funcția principală public static void main(String[] args) { // Intrare șir String A = 'geeks'; // Convertiți șirul în minuscule A = A.toLowerCase(); boolean str = isPalindrom(A); System.out.println(str); } }>>>   
  Ieșire   
false 
    
 Complexitatea metodei de mai sus:  
 
 
    Complexitatea timpului:     Complexitatea de timp a codului dat este O(n), unde n este lungimea șirului de intrare. Acest lucru se datorează faptului că funcția `isPalindrom` se apelează recursiv pentru caracterele din pozițiile (i+1, j-1) până când pointerii i și j se încrucișează sau caracterele de la pointeri nu sunt egale. Deoarece comparăm fiecare caracter din șir exact o dată, complexitatea timpului este O(n).  
  
    Complexitatea spațiului:     Complexitatea spațială a codului este O(n), unde n este lungimea șirului de intrare. Acest lucru se datorează faptului că fiecare apel recursiv creează un nou cadru de stivă care stochează valorile curente ale parametrilor funcției și ale variabilelor locale. În cel mai rău caz, stiva de apeluri de funcție poate crește până la n/2 (când șirul de intrare este un palindrom), deci complexitatea spațiului este O(n).  
  
 
 4. Utilizarea StringBuilder Approach în Java  
 
 În această abordare,  
  
 
 În primul rând, luăm intrarea String de la utilizator.  
 
 Apoi creăm obiectul Stringbuilder str1″și stocăm valoarea String în el.  
 
 Metoda reverse() din Stringbuider ne oferă șirul invers. Ee stochează acel șir invers în str1.  
 
 Cu ajutorul metodei equals() comparăm valorile șirului, cu ajutorul condiției if și else, verificăm dacă valoarea șirului este similară sau nu.  
 
 
 Mai jos este implementarea abordării de mai sus:  
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'); } } } 
    
  Ieșire       Complexitatea codului de mai sus:     
  
 
    Complexitatea timpului:     Complexitatea de timp a codului este O(n), unde n este din nou lungimea șirului de intrare str. Factorul principal care contribuie la această complexitate temporală este inversarea șirului folosind str1.reverse(). Inversarea unui șir în acest mod are o complexitate de timp de O(n), unde n este lungimea șirului. Alte operațiuni din cod, cum ar fi citirea intrării și compararea șirurilor, sunt operațiuni în timp constant și nu afectează semnificativ complexitatea generală a timpului.  
  
    Complexitatea spațiului:     Complexitatea spațială a codului Java dat este O(n), unde n este lungimea șirului de intrare str. Acest lucru se datorează faptului că codul folosește un StringBuilder pentru a stoca o copie inversată a șirului de intrare, iar spațiul necesar pentru StringBuilder este proporțional cu lungimea șirului de intrare.  
  
 
 Referinţă  
 
 
 Pentru a afla mai multe despre Palindrom, consultați   Program pentru String Palindrome   .