Eksempel 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 

Kompleksiteten af ​​ovenstående metode:

Tidskompleksitet: Tidskompleksiteten af ​​den givne kode er O(n), hvor n er længden af ​​inputstrengen. Dette skyldes, at while-løkken itererer gennem halvdelen af ​​strengen for at kontrollere, om det er et palindrom. Da vi kun tjekker halvdelen af ​​strengen, er antallet af iterationer proportionalt med n/2, som er O(n).

Rumkompleksitet: Kodens pladskompleksitet er O(1), fordi koden kun bruger en konstant mængde ekstra plads, der er uafhængig af inputstørrelsen. De eneste variabler, der bruges i koden, er i, j og str, som hver optager en konstant mængde plads. Der oprettes ikke yderligere plads i koden.

Eksempel 2:

// 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 

Kompleksiteten af ​​ovenstående metode:

Tidskompleksitet: Tidskompleksiteten af ​​den givne kode er O(n), hvor n er længden af ​​inputstrengen. Dette skyldes, at while-løkken i `isPalindrome`-metoden itererer gennem halvdelen af ​​strengen for at kontrollere, om det er et palindrom. Da vi kun tjekker halvdelen af ​​strengen, er antallet af iterationer proportionalt med n/2, som er O(n).

Rumkompleksitet: Kodens pladskompleksitet er O(1), fordi koden kun bruger en konstant mængde ekstra plads, der er uafhængig af inputstørrelsen. De eneste variabler, der bruges i koden, er i, j, str og str2, som hver optager en konstant mængde plads. Der oprettes ikke yderligere plads i koden.

3. Rekursiv tilgang til P alindrome-program i Java

Fremgangsmåden er meget enkel. Ligesom to-pointer tilgangen, vil vi kontrollere den første og den sidste værdi af strengen, men denne gang vil det være gennem rekursion.

• Vi vil tage to pointere i, der peger på begyndelsen af ​​strengen og j, der peger mod slutningen af ​​strengen.
• Fortsæt med at øge i og dekrementere j, mens i
• Kontroller, om tegnene ved disse pointer er de samme eller ej. Vi gør dette gennem rekursion – (i+1, j-1
• Hvis alle tegnene er ens på ith og jth indekset, indtil i>=j betingelsen opfylder, udskriv true else false.

Nedenfor er implementeringen af ​​ovenstående tilgang:

// 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; } // sammenligner tegnene på disse pointere if (A.charAt(i) != A.charAt(j)) { return false; } // kontrollerer alt igen rekursivt returnerer isPalindrome(i + 1, j - 1, A); } public static boolean isPalindrome(String A) { return isPalindrome(0, A.length() - 1, A); } // hovedfunktion public static void main(String[] args) { // Input string String A = 'geeks'; // Konverter strengen til små bogstaver A = A.toLowerCase(); boolsk str = isPalindrom(A); System.out.println(str); } } 

false 

Kompleksiteten af ​​ovenstående metode:

Tidskompleksitet: Tidskompleksiteten af ​​den givne kode er O(n), hvor n er længden af ​​inputstrengen. Dette skyldes, at `isPalindrome`-funktionen rekursivt kalder sig selv for tegnene på positionerne (i+1, j-1), indtil pointerne i og j krydser hinanden, eller tegnene ved pointerne ikke er ens. Da vi sammenligner hvert tegn i strengen nøjagtigt én gang, er tidskompleksiteten O(n).

Rumkompleksitet: Kodens rumkompleksitet er O(n), hvor n er længden af ​​inputstrengen. Dette skyldes, at hvert rekursivt kald opretter en ny stakramme, der gemmer de aktuelle værdier af funktionsparametrene og lokale variabler. I værste fald kan funktionskaldsstakken vokse så stor som n/2 (når inputstrengen er et palindrom), så rumkompleksiteten er O(n).

4. Brug af StringBuilder Approach i Java

I denne tilgang

• Først tager vi String-inputtet fra brugeren.
• Derefter opretter vi Stringbuilder-objektet str1″og gemmer værdien af ​​String i det.
• Reverse()-metoden i Stringbuider giver os den omvendte streng. Ee gemme den omvendte streng i str1.
• Ved hjælp af equals()-metoden sammenligner vi strengens værdier, ved hjælp af if og else condition check, at strengværdien er ens eller ej.

Nedenfor er implementeringen af ​​ovenstående tilgang:

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 

Kompleksiteten af ​​ovenstående kode:

Tidskompleksitet: Kodens tidskompleksitet er O(n), hvor n igen er længden af ​​inputstrengen str. Den primære faktor, der bidrager til denne tidskompleksitet, er vendingen af ​​strengen ved hjælp af str1.reverse(). At vende en streng på denne måde har en tidskompleksitet på O(n), hvor n er længden af ​​strengen. Andre operationer i koden, såsom læsning af input og sammenligning af strenge, er konstant-tidsoperationer og påvirker ikke den samlede tidskompleksitet væsentligt.

Rumkompleksitet: Rumkompleksiteten af ​​den givne Java-kode er O(n), hvor n er længden af ​​inputstrengen str. Dette skyldes, at koden bruger en StringBuilder til at gemme en omvendt kopi af inputstrengen, og den nødvendige plads til StringBuilder er proportional med længden af ​​inputstrengen.

Reference

For at vide mere om Palindrom henvises til Program for strengpalindrom .