Esempio 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 

La complessità del metodo di cui sopra:

Complessità temporale: La complessità temporale del codice specificato è O(n), dove n è la lunghezza della stringa di input. Questo perché il ciclo while scorre metà della stringa per verificare se è palindromo. Dato che controlliamo solo metà della stringa, il numero di iterazioni è proporzionale a n/2, che è O(n).

Complessità spaziale: La complessità spaziale del codice è O(1), poiché il codice utilizza solo una quantità costante di spazio aggiuntivo indipendente dalla dimensione dell'input. Le uniche variabili utilizzate nel codice sono i, j e str, ciascuna delle quali occupa una quantità costante di spazio. Non viene creato spazio aggiuntivo nel codice.

Esempio 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 

La complessità del metodo di cui sopra:

Complessità temporale: La complessità temporale del codice specificato è O(n), dove n è la lunghezza della stringa di input. Questo perché il ciclo while nel metodo `isPalindrome` scorre metà della stringa per verificare se è palindromo. Dato che controlliamo solo metà della stringa, il numero di iterazioni è proporzionale a n/2, che è O(n).

Complessità spaziale: La complessità spaziale del codice è O(1), poiché il codice utilizza solo una quantità costante di spazio aggiuntivo indipendente dalla dimensione dell'input. Le uniche variabili utilizzate nel codice sono i, j, str e str2, ciascuna delle quali occupa una quantità costante di spazio. Non viene creato spazio aggiuntivo nel codice.

3. Approccio ricorsivo per P Programma alindrome in Java

L'approccio è molto semplice. Proprio come nell'approccio a due puntatori, controlleremo il primo e l'ultimo valore della stringa, ma questa volta avverrà tramite la ricorsione.

• Prenderemo due puntatori i che puntano all'inizio della stringa e j che puntano alla fine della stringa.
• Continua ad incrementare i e a diminuire j mentre i
• Controlla se i caratteri in questi puntatori sono gli stessi o meno. Lo stiamo facendo attraverso la ricorsione – (i+1, j-1
• Se tutti i caratteri sono uguali sull'indice i-esimo e j-esimo finché la condizione i>=j non è soddisfatta, stampa vero altrimenti falso.

Di seguito è riportata l’implementazione dell’approccio di cui sopra:

// 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) { restituisce vero; } // confrontando i caratteri su questi puntatori if (A.charAt(i) != A.charAt(j)) { return false; } // controllando di nuovo tutto in modo ricorsivo return isPalindrome(i + 1, j - 1, A); } public static boolean isPalindrome(String A) { return isPalindrome(0, A.length() - 1, A); } // funzione principale public static void main(String[] args) { // Stringa di input String A = 'geeks'; // Converti la stringa in minuscolo A = A.toLowerCase(); booleano str = isPalindromo(A); System.out.println(str); } } 

false 

La complessità del metodo di cui sopra:

Complessità temporale: La complessità temporale del codice specificato è O(n), dove n è la lunghezza della stringa di input. Questo perché la funzione 'isPalindrome' richiama se stessa ricorsivamente per i caratteri nelle posizioni (i+1, j-1) fino a quando i puntatori i e j si incrociano o i caratteri sui puntatori non sono uguali. Poiché confrontiamo ogni carattere nella stringa esattamente una volta, la complessità temporale è O(n).

Complessità spaziale: La complessità spaziale del codice è O(n), dove n è la lunghezza della stringa di input. Questo perché ogni chiamata ricorsiva crea un nuovo stack frame che memorizza i valori correnti dei parametri della funzione e delle variabili locali. Nel peggiore dei casi, lo stack di chiamate della funzione può crescere fino a n/2 (quando la stringa di input è un palindromo), quindi la complessità dello spazio è O(n).

4. Utilizzo dell'approccio StringBuilder in Java

In questo approccio,

• Innanzitutto, prendiamo l'input String dall'utente.
• Quindi creiamo l'oggetto Stringbuilder str1″e memorizziamo il valore di String al suo interno.
• Il metodo reverse() in Stringbuilder ci fornisce la stringa inversa. Ee memorizza quella stringa inversa in str1.
• Con l'aiuto del metodo equals() confrontiamo i valori della stringa, con l'aiuto delle condizioni if ​​e else controlliamo che il valore della stringa sia simile o meno.

Di seguito è riportata l’implementazione dell’approccio di cui sopra:

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 

La complessità del suddetto Codice:

Complessità temporale: La complessità temporale del codice è O(n), dove n è ancora la lunghezza della stringa di input str. Il fattore principale che contribuisce a questa complessità temporale è l'inversione della stringa utilizzando str1.reverse(). L'inversione di una stringa in questo modo ha una complessità temporale pari a O(n), dove n è la lunghezza della stringa. Altre operazioni nel codice, come la lettura dell'input e il confronto delle stringhe, sono operazioni a tempo costante e non influiscono in modo significativo sulla complessità temporale complessiva.

Complessità spaziale: La complessità spaziale del codice Java specificato è O(n), dove n è la lunghezza della stringa di input str. Questo perché il codice utilizza un StringBuilder per archiviare una copia invertita della stringa di input e lo spazio richiesto per StringBuilder è proporzionale alla lunghezza della stringa di input.

Riferimento

Per saperne di più sul palindromo fare riferimento Programma per palindromo di stringhe .