Exemple 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 complexité de la méthode ci-dessus :

Complexité temporelle : La complexité temporelle du code donné est O(n), où n est la longueur de la chaîne d'entrée. En effet, la boucle while parcourt la moitié de la chaîne pour vérifier s'il s'agit d'un palindrome. Puisque nous ne vérifions que la moitié de la chaîne, le nombre d’itérations est proportionnel à n/2, ce qui correspond à O(n).

exemple de nom d'utilisateur

Complexité spatiale : La complexité spatiale du code est O(1), car le code n'utilise qu'une quantité constante d'espace supplémentaire indépendante de la taille d'entrée. Les seules variables utilisées dans le code sont i, j et str, qui occupent chacune une quantité d'espace constante. Aucun espace supplémentaire n'est créé dans le code.

Exemple 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 complexité de la méthode ci-dessus :

Complexité temporelle : La complexité temporelle du code donné est O(n), où n est la longueur de la chaîne d'entrée. En effet, la boucle while de la méthode `isPalindrome` parcourt la moitié de la chaîne pour vérifier s'il s'agit d'un palindrome. Puisque nous ne vérifions que la moitié de la chaîne, le nombre d’itérations est proportionnel à n/2, ce qui correspond à O(n).

Complexité spatiale : La complexité spatiale du code est O(1), car le code n'utilise qu'une quantité constante d'espace supplémentaire indépendante de la taille d'entrée. Les seules variables utilisées dans le code sont i, j, str et str2, qui occupent chacune une quantité d'espace constante. Aucun espace supplémentaire n'est créé dans le code.

3. Approche récursive pour P Programme alindrome en Java

L'approche est très simple. Tout comme pour l’approche à deux pointeurs, nous vérifierons la première et la dernière valeur de la chaîne mais cette fois ce sera par récursion.

• Nous prendrons deux pointeurs i pointant vers le début de la chaîne et j pointant vers la fin de la chaîne.
• Continuez à incrémenter i et à décrémenter j pendant que je
• Vérifiez si les caractères de ces pointeurs sont identiques ou non. Nous faisons cela par récursivité – (i+1, j-1
• Si tous les caractères sont les mêmes sur les ième et jième index jusqu'à ce que la condition i>=j soit satisfaite, imprimez vrai sinon faux.

Vous trouverez ci-dessous la mise en œuvre de l’approche ci-dessus :

// 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) { renvoie vrai ; } // comparaison des caractères sur ces pointeurs if (A.charAt(i) != A.charAt(j)) { return false; } // tout vérifier à nouveau de manière récursive return isPalindrome(i + 1, j - 1, A); } public static boolean isPalindrome(String A) { return isPalindrome(0, A.length() - 1, A); } // fonction principale public static void main(String[] args) { // Chaîne d'entrée String A = 'geeks'; // Convertit la chaîne en minuscules A = A.toLowerCase(); boolean str = isPalindrome(A); System.out.println(str); } }>

false>

La complexité de la méthode ci-dessus :

Complexité temporelle : La complexité temporelle du code donné est O(n), où n est la longueur de la chaîne d'entrée. En effet, la fonction `isPalindrome` s'appelle récursivement pour les caractères aux positions (i+1, j-1) jusqu'à ce que les pointeurs i et j se croisent ou que les caractères aux pointeurs ne soient pas égaux. Puisque nous comparons chaque caractère de la chaîne exactement une fois, la complexité temporelle est O(n).

fonctionnalités de java8

Complexité spatiale : La complexité spatiale du code est O(n), où n est la longueur de la chaîne d'entrée. En effet, chaque appel récursif crée un nouveau cadre de pile qui stocke les valeurs actuelles des paramètres de fonction et des variables locales. Dans le pire des cas, la pile d'appels de fonction peut atteindre n/2 (lorsque la chaîne d'entrée est un palindrome), donc la complexité spatiale est O(n).

4. Utilisation de l'approche StringBuilder en Java

Dans cette approche,

• Tout d’abord, nous prenons l’entrée String de l’utilisateur.
• Ensuite, nous créons l'objet Stringbuilder str1″ et y stockons la valeur de String.
• La méthode reverse() dans Stringbuilder nous donne la chaîne inversée. Ee stocke cette chaîne inversée dans str1.
• À l’aide de la méthode equals(), nous comparons les valeurs de la chaîne, à l’aide des conditions if et else, vérifions que la valeur de la chaîne est similaire ou non.

Vous trouverez ci-dessous la mise en œuvre de l’approche ci-dessus :

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 complexité du code ci-dessus :

Complexité temporelle : La complexité temporelle du code est O(n), où n est à nouveau la longueur de la chaîne d'entrée str. Le principal facteur contribuant à cette complexité temporelle est l'inversion de la chaîne à l'aide de str1.reverse(). Inverser une chaîne de cette manière a une complexité temporelle de O(n), où n est la longueur de la chaîne. D'autres opérations dans le code, telles que la lecture de l'entrée et la comparaison des chaînes, sont des opérations à temps constant et n'ont pas d'impact significatif sur la complexité temporelle globale.

mylivecricket pour le cricket en direct

Complexité spatiale : La complexité spatiale du code Java donné est O(n), où n est la longueur de la chaîne d'entrée str. En effet, le code utilise un StringBuilder pour stocker une copie inversée de la chaîne d'entrée et l'espace requis pour le StringBuilder est proportionnel à la longueur de la chaîne d'entrée.

Référence

Pour en savoir plus sur Palindrome, référez-vous Programme pour le palindrome à cordes .