Primer 1:

// 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'); } }>

No>

Kompleksnost zgornje metode:

Časovna zapletenost: Časovna kompleksnost dane kode je O(n), kjer je n dolžina vhodnega niza. To je zato, ker zanka while ponovi polovico niza, da preveri, ali je palindrom. Ker preverimo samo polovico niza, je število ponovitev sorazmerno z n/2, kar je O(n).

Kompleksnost prostora: Prostorska kompleksnost kode je O(1), ker koda uporablja samo stalno količino dodatnega prostora, ki je neodvisen od velikosti vnosa. Edine spremenljivke, uporabljene v kodi, so i, j in str, od katerih vsaka zavzame konstantno količino prostora. V kodi ni ustvarjen dodaten prostor.

Primer 2:

naročanje po pošti

// 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'); } }>

String 1 :It is not a palindrome String 2 :It is a palindrome>

Kompleksnost zgornje metode:

Časovna zapletenost: Časovna kompleksnost dane kode je O(n), kjer je n dolžina vhodnega niza. To je zato, ker zanka while v metodi `isPalindrome` ponovi polovico niza, da preveri, ali je palindrom. Ker preverimo samo polovico niza, je število ponovitev sorazmerno z n/2, kar je O(n).

Kompleksnost prostora: Prostorska kompleksnost kode je O(1), ker koda uporablja samo stalno količino dodatnega prostora, ki je neodvisen od velikosti vnosa. Edine spremenljivke, uporabljene v kodi, so i, j, str in str2, od katerih vsaka zavzame konstantno količino prostora. V kodi ni ustvarjen dodaten prostor.

java inicializira matriko

3. Rekurzivni pristop za P program alindrome v Javi

Pristop je zelo preprost. Tako kot pri pristopu z dvema kazalcema, bomo preverili prvo in zadnjo vrednost niza, vendar bo tokrat z rekurzijo.

• Vzamemo dva kazalca i, ki kažeta na začetek niza, in j, ki kažeta na konec niza.
• Povečujte i in zmanjšujte j, medtem ko i
• Preverite, ali so znaki na teh kazalcih enaki ali ne. To počnemo z rekurzijo – (i+1, j-1
• Če so vsi znaki enaki na i-tem in j-tem indeksu, dokler ni izpolnjen pogoj i>=j, natisnite true else false.

Spodaj je izvedba zgornjega pristopa:

// 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; } // primerjava znakov na teh kazalcih if (A.charAt(i) != A.charAt(j)) { return false; } // ponovno rekurzivno preverjanje vsega return isPalindrome(i + 1, j - 1, A); } public static boolean isPalindrome(String A) { return isPalindrome(0, A.length() - 1, A); } // glavna funkcija public static void main(String[] args) { // Vhodni niz String A = 'geeks'; // Pretvori niz v male črke A = A.toLowerCase(); boolean str = isPalindrome(A); System.out.println(str); } }>

false>

Kompleksnost zgornje metode:

Časovna zapletenost: Časovna kompleksnost dane kode je O(n), kjer je n dolžina vhodnega niza. To je zato, ker funkcija `isPalindrome` rekurzivno kliče samo sebe za znake na položajih (i+1, j-1), dokler se kazalca i in j ne prekrižata ali pa znaka na kazalcih nista enaka. Ker vsak znak v nizu primerjamo natanko enkrat, je časovna kompleksnost O(n).

Kompleksnost prostora: Prostorska kompleksnost kode je O(n), kjer je n dolžina vhodnega niza. To je zato, ker vsak rekurzivni klic ustvari nov okvir sklada, ki shrani trenutne vrednosti funkcijskih parametrov in lokalnih spremenljivk. V najslabšem primeru lahko sklad klicev funkcij naraste do n/2 (ko je vhodni niz palindrom), tako da je kompleksnost prostora O(n).

blokiranih stikov

4. Uporaba pristopa StringBuilder v Javi

Pri tem pristopu,

• Najprej vzamemo niz od uporabnika.
• Nato ustvarimo objekt Stringbuilder str1″in vanj shranimo vrednost niza.
• Metoda reverse() v Stringbuiderju nam daje obratni niz. Ee shranite ta obratni niz v str1.
• S pomočjo metode equals() primerjamo vrednosti niza, s pomočjo if in else pogoja preverimo ali so vrednosti niza podobne ali ne.

Spodaj je izvedba zgornjega pristopa:

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'); } } }>

Not a palindrome String>

Kompleksnost zgornje kode:

Časovna zapletenost: Časovna kompleksnost kode je O(n), kjer je n spet dolžina vhodnega niza str. Glavni dejavnik, ki prispeva k tej časovni kompleksnosti, je obračanje niza z uporabo str1.reverse(). Obračanje niza na ta način ima časovno kompleksnost O(n), kjer je n dolžina niza. Druge operacije v kodi, kot sta branje vnosa in primerjava nizov, so operacije v konstantnem času in ne vplivajo bistveno na celotno časovno kompleksnost.

Kompleksnost prostora: Prostorska kompleksnost dane kode Java je O(n), kjer je n dolžina vhodnega niza str. To je zato, ker koda uporablja StringBuilder za shranjevanje obrnjene kopije vhodnega niza, prostor, potreben za StringBuilder, pa je sorazmeren z dolžino vhodnega niza.

Referenca

Če želite izvedeti več o Palindromu, glejte Program za String Palindrome .