Sakoma, kad eilutė yra palindromas, jei ji yra tokia pati, jei pradedame ją skaityti iš kairės į dešinę arba iš dešinės į kairę. Šiame straipsnyje sužinosime, kaip patikrinti, ar eilutė yra „Java“ palindromas.

Taigi panagrinėkime eilutę str , dabar užduotis yra tik išsiaiškinti, ar jos atvirkštinė eilutė yra tokia pati, kaip ir yra.

Palindromo pavyzdys:

Įvestis: str = abba
Išvestis: Taip

Įvestis: str = geeks
Išvestis: Nr

Palindromo eilutės metodai Java

Yra trys pagrindiniai metodai, kaip patikrinti eilutės palindromą „Java“, kaip nurodyta toliau:

1. Naivus metodas
2. Dviejų rodyklių metodas
3. Rekursyvinis metodas
4. Naudojant StringBuilder

1. Naivus būdas patikrinti palindromo eilutę Java

Apversdami pateiktą eilutę ir palygindami. Galime patikrinti, ar nurodyta eilutė yra palindromas, palyginę pradinę eilutę su atvirkštine versija.

Toliau pateikiamas pirmiau minėto metodo įgyvendinimas:

// 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); } // Tikrinama, ar abi eilutės yra lygios if (str.equals(rev)) { ans = true; } return ans; } public static void main(String[] args) { // Įvesties eilutė String str = 'geeks'; // Konvertuoti eilutę į mažąsias raides str = str.toLowerCase(); loginis A = isPalindromas(str); System.out.println(A); } }>>   
  Išvestis   
false 
    
 Pirmiau nurodyto metodo sudėtingumas:  
 
 
    Laiko sudėtingumas:     Pateikto kodo sudėtingumas laike yra O(n), kur n yra įvesties eilutės ilgis. Taip yra todėl, kad ciklas for kartoja kiekvieną eilutės simbolį vieną kartą, kad sukurtų atvirkštinę eilutę.  
  
    Erdvės sudėtingumas:     Kodo erdvės sudėtingumas yra O(n), kur n yra įvesties eilutės ilgis. Taip yra todėl, kad atvirkštinė eilutė sukuriama ir saugoma atskirame eilutės kintamajame, kuris užima vietos atmintyje proporcingai įvesties eilutės ilgiui. Be to, kiti kode naudojami kintamieji (i, str ir ans) užima pastovią erdvę, kuri nepriklauso nuo įvesties dydžio.  
  
 
 Aukščiau pateiktame pavyzdyje, jei rašome     ABba     vietoj     abba     , tada taip pat turėtume gauti išvestį kaip     taip     . Taigi, prieš tikrindami, ar nėra palindromo, turime pakeisti eilutės didžiąsias arba mažąsias raides. Jei to nepadarysime, sulauksime netikėtų rezultatų. Taip yra todėl, kad kompiliatorius tikrina simbolius pagal juos     ASCII     vertė ir     ASCII     vertė     A     nėra tas pats kaip     a     .  
  
    2. Dviejų rodyklių metodas P     alindromo programa Java  
 
 Mūsų požiūris bus toks, kad pirmiausia eilutę konvertuosime į mažąsias raides. Tada paimsime du patarimus     i     rodydamas į eilutės pradžią ir     j     rodydamas į eilutės galą. Toliau didinkite     i     ir mažėja     j     kol     i        ir kiekviename žingsnyje patikrinkite, ar šių rodyklių simboliai yra vienodi, ar ne. Jei ne, tada styga nėra palindromas.   
   
    1 pavyzdys:     
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'); } } 
    
  Išvestis       Laiko sudėtingumas:     Pateikto kodo sudėtingumas laike yra O(n), kur n yra įvesties eilutės ilgis. Taip yra todėl, kad while ciklas kartojasi per pusę eilutės, kad patikrintų, ar tai palindromas. Kadangi tikriname tik pusę eilutės, iteracijų skaičius yra proporcingas n/2, tai yra O(n).  
  
    Erdvės sudėtingumas:     Kodo erdvės sudėtingumas yra O(1), nes kodas naudoja tik pastovų papildomos vietos kiekį, kuris nepriklauso nuo įvesties dydžio. Vieninteliai kode naudojami kintamieji yra i, j ir str, kurių kiekvienas užima pastovų kiekį vietos. Kode papildomos vietos nesukuriama.  
   
    2 pavyzdys:     
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'); } } 
    
  Išvestis   
String 1 :It is not a palindrome String 2 :It is a palindrome 
  
 Pirmiau minėto metodo sudėtingumas:  
 
 
    Laiko sudėtingumas:     Pateikto kodo sudėtingumas laike yra O(n), kur n yra įvesties eilutės ilgis. Taip yra todėl, kad „isPalindromo“ metodo while ciklas kartojasi per pusę eilutės, kad patikrintų, ar tai palindromas. Kadangi tikriname tik pusę eilutės, iteracijų skaičius yra proporcingas n/2, tai yra O(n).  
  
    Erdvės sudėtingumas:     Kodo erdvės sudėtingumas yra O(1), nes kodas naudoja tik pastovų papildomos vietos kiekį, kuris nepriklauso nuo įvesties dydžio. Vieninteliai kode naudojami kintamieji yra i, j, str ir str2, kurių kiekvienas užima pastoviai daug vietos. Kode papildomos vietos nesukuriama.  
  
 
    3. Rekursyvus požiūris į P     alindromo programa Java  
 
 Metodas labai paprastas. Kaip ir taikant dviejų žymeklių metodą, mes patikrinsime pirmąją ir paskutinę eilutės reikšmes, tačiau šį kartą tai bus atliekama naudojant rekursiją.  
  
 
 Paimsime dvi rodykles i, nukreipiančias į eilutės pradžią, ir j, rodančias į eilutės pabaigą.  
 
 Toliau didinkite i ir mažinkite j, kol i    
 
 Patikrinkite, ar šių rodyklių simboliai yra vienodi, ar ne. Tai darome per rekursiją – (i+1, j-1  
 
 Jei visi simboliai yra vienodi i-oje ir j-ojoje indeksuose, kol i>=j sąlyga netenkinama, spausdinkite teisingą, kitaip false.  
 
 
    Toliau pateikiamas pirmiau minėto metodo įgyvendinimas:     
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; } // tų rodyklių simbolių palyginimas if (A.charAt(i) != A.charAt(j)) { return false; } // dar kartą viską tikrinant rekursyviai return isPalindromas(i + 1, j - 1, A); } public static boolean isPalindromas(String A) { return isPalindromas(0, A.length() - 1, A); } // pagrindinė funkcija public static void main(String[] args) { // Įvesties eilutė String A = 'geeks'; // Konvertuoti eilutę į mažąsias raides A = A.toLowerCase(); loginis str = isPalindromas(A); System.out.println(str); } }>>   
  Išvestis   
false 
    
 Pirmiau minėto metodo sudėtingumas:  
 
 
    Laiko sudėtingumas:     Pateikto kodo sudėtingumas laike yra O(n), kur n yra įvesties eilutės ilgis. Taip yra todėl, kad funkcija „isPalindromas“ rekursyviai iškviečia save pozicijose (i+1, j-1) esantiems simboliams, kol rodyklės i ir j susikerta viena su kita arba rodyklėse esantys simboliai nėra lygūs. Kadangi kiekvieną eilutės simbolį lyginame tiksliai vieną kartą, laiko sudėtingumas yra O(n).  
  
    Erdvės sudėtingumas:     Kodo erdvės sudėtingumas yra O(n), kur n yra įvesties eilutės ilgis. Taip yra todėl, kad kiekvienas rekursinis iškvietimas sukuria naują dėklo rėmelį, kuriame saugomos esamos funkcijos parametrų ir vietinių kintamųjų reikšmės. Blogiausiu atveju funkcijų iškvietimo krūva gali išaugti iki n/2 (kai įvesties eilutė yra palindromas), todėl erdvės sudėtingumas yra O(n).  
  
 
 4. StringBuilder metodo naudojimas Java programoje  
 
 Taikant šį požiūrį,  
  
 
 Pirmiausia iš vartotojo paimame eilutės įvestį.  
 
 Tada sukuriame Stringbuilder objektą str1″ ir išsaugome jame String reikšmę.  
 
 Reverse () metodas Stringbuider suteikia mums atvirkštinę eilutę. Išsaugokite atvirkštinę eilutę str1.  
 
 Naudodami equals() metodą palyginame eilutės reikšmes, o su sąlyga if ir else patikriname, ar eilutės reikšmės panašios, ar ne.  
 
 
 Toliau pateikiamas pirmiau minėto metodo įgyvendinimas:  
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'); } } } 
    
  Išvestis       Pirmiau pateikto kodo sudėtingumas:     
  
 
    Laiko sudėtingumas:     Kodo laiko sudėtingumas yra O(n), kur n vėl yra įvesties eilutės str ilgis. Pagrindinis veiksnys, prisidedantis prie šio laiko sudėtingumo, yra eilutės apvertimas naudojant str1.reverse(). Tokiu būdu apverčiant eilutę, laiko sudėtingumas yra O(n), kur n yra eilutės ilgis. Kitos kode operacijos, pvz., įvesties skaitymas ir eilučių palyginimas, yra pastovaus laiko operacijos ir neturi didelės įtakos bendram laiko sudėtingumui.  
  
    Erdvės sudėtingumas:     Pateikto Java kodo erdvės sudėtingumas yra O(n), kur n yra įvesties eilutės str ilgis. Taip yra todėl, kad kodas naudoja StringBuilder atvirkštinei įvesties eilutės kopijai saugoti, o StringBuilder reikalinga vieta yra proporcinga įvesties eilutės ilgiui.  
  
 
 Nuoroda  
 
 
 Norėdami sužinoti daugiau apie Palindromą, žr   Styginių palindromo programa   .