Przykład 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 

Złożoność powyższej metody:

Złożoność czasowa: Złożoność czasowa danego kodu wynosi O(n), gdzie n jest długością ciągu wejściowego. Dzieje się tak, ponieważ pętla while iteruje przez połowę łańcucha, aby sprawdzić, czy jest to palindrom. Ponieważ sprawdzamy tylko połowę ciągu, liczba iteracji jest proporcjonalna do n/2, czyli O(n).

Złożoność przestrzeni: Złożoność przestrzenna kodu wynosi O(1), ponieważ kod wykorzystuje tylko stałą ilość dodatkowej przestrzeni, która jest niezależna od rozmiaru wejściowego. Jedynymi zmiennymi używanymi w kodzie są i, j i str, z których każda zajmuje stałą ilość miejsca. W kodzie nie jest tworzona żadna dodatkowa spacja.

Przykład 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 

Złożoność powyższej metody:

Złożoność czasowa: Złożoność czasowa danego kodu wynosi O(n), gdzie n jest długością ciągu wejściowego. Dzieje się tak, ponieważ pętla while w metodzie „isPalindrome” iteruje przez połowę łańcucha, aby sprawdzić, czy jest to palindrom. Ponieważ sprawdzamy tylko połowę ciągu, liczba iteracji jest proporcjonalna do n/2, czyli O(n).

Złożoność przestrzeni: Złożoność przestrzenna kodu wynosi O(1), ponieważ kod wykorzystuje tylko stałą ilość dodatkowej przestrzeni, która jest niezależna od rozmiaru wejściowego. Jedynymi zmiennymi używanymi w kodzie są i, j, str i str2, z których każda zajmuje stałą ilość miejsca. W kodzie nie jest tworzona żadna dodatkowa spacja.

3. Podejście rekurencyjne dla P Program alindromu w Javie

Podejście jest bardzo proste. Podobnie jak w przypadku podejścia dwuwskaźnikowego, sprawdzimy pierwszą i ostatnią wartość ciągu, ale tym razem będzie to poprzez rekurencję.

• Weźmiemy dwa wskaźniki i wskazujące na początek łańcucha i j wskazujące na koniec łańcucha.
• Zwiększaj i i zmniejszaj j podczas i
• Sprawdź, czy znaki w tych wskaźnikach są takie same, czy nie. Robimy to poprzez rekurencję – (i+1, j-1
• Jeśli wszystkie znaki w i-tym i j-tym indeksie są takie same, aż do spełnienia warunku i>=j, wypisz wartość true w przeciwnym razie wartość false.

Poniżej implementacja powyższego podejścia:

// 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) { zwróć wartość true; } // porównywanie znaków na tych wskaźnikach if (A.charAt(i) != A.charAt(j)) { return false; } // ponowne sprawdzenie wszystkiego rekurencyjnie return isPalindrome(i + 1, j - 1, A); } public static boolean isPalindrome(String A) { return isPalindrome(0, A.length() - 1, A); } // funkcja główna public static void main(String[] args) { // Ciąg wejściowy String A = 'geeks'; // Konwertuj ciąg na małe litery A = A.toLowerCase(); wartość logiczna str = isPalindrom(A); System.out.println(str); } } 

false 

Złożoność powyższej metody:

Złożoność czasowa: Złożoność czasowa danego kodu wynosi O(n), gdzie n jest długością ciągu wejściowego. Dzieje się tak, ponieważ funkcja „isPalindrome” wywołuje się rekurencyjnie dla znaków na pozycjach (i+1, j-1), dopóki wskaźniki i i j nie przetną się lub znaki na wskaźnikach nie będą równe. Ponieważ każdy znak w ciągu porównujemy dokładnie raz, złożoność czasowa wynosi O(n).

Złożoność przestrzeni: Złożoność przestrzenna kodu wynosi O(n), gdzie n jest długością ciągu wejściowego. Dzieje się tak, ponieważ każde wywołanie rekurencyjne tworzy nową ramkę stosu, w której przechowywane są bieżące wartości parametrów funkcji i zmiennych lokalnych. W najgorszym przypadku stos wywołań funkcji może urosnąć do n/2 (kiedy ciąg wejściowy jest palindromem), więc złożoność przestrzenna wynosi O(n).

4. Wykorzystanie podejścia StringBuilder w Javie

W tym podejściu

• Najpierw pobieramy od użytkownika dane wejściowe typu String.
• Następnie tworzymy obiekt Stringbuilder str1″ i przechowujemy w nim wartość String.
• Metoda Reverse() w Stringbuider daje nam odwrotny String. Ee zapisz ten odwrotny ciąg w str1.
• Za pomocą metody równości() porównujemy wartość łańcucha, za pomocą warunków if i else sprawdzamy, czy wartości ciągu są podobne, czy nie.

Poniżej implementacja powyższego podejścia:

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 

Złożoność powyższego Kodeksu:

Złożoność czasowa: Złożoność czasowa kodu wynosi O(n), gdzie n jest ponownie długością ciągu wejściowego str. Głównym czynnikiem wpływającym na tę złożoność czasową jest odwrócenie łańcucha za pomocą str1.reverse(). Odwrócenie łańcucha w ten sposób ma złożoność czasową O(n), gdzie n jest długością łańcucha. Inne operacje w kodzie, takie jak odczytywanie danych wejściowych i porównywanie ciągów znaków, są operacjami wykonywanymi w czasie stałym i nie wpływają znacząco na ogólną złożoność czasową.

Złożoność przestrzeni: Złożoność przestrzenna danego kodu Java wynosi O(n), gdzie n jest długością ciągu wejściowego str. Dzieje się tak, ponieważ kod używa StringBuilder do przechowywania odwróconej kopii ciągu wejściowego, a miejsce wymagane dla StringBuilder jest proporcjonalne do długości ciągu wejściowego.

Odniesienie

Aby dowiedzieć się więcej o Palindromie, zobacz Program dla palindromu strunowego .