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 til metoden ovenfor:

Tidskompleksitet: Tidskompleksiteten til den gitte koden er O(n), der n er lengden på inndatastrengen. Dette er fordi while-løkken itererer gjennom halvparten av strengen for å sjekke om det er et palindrom. Siden vi bare sjekker halvparten av strengen, er antall iterasjoner proporsjonalt med n/2, som er O(n).

Plass kompleksitet: Kodens plasskompleksitet er O(1), fordi koden bare bruker en konstant mengde ekstra plass som er uavhengig av inngangsstørrelsen. De eneste variablene som brukes i koden er i, j og str, som hver tar opp en konstant mengde plass. Ingen ekstra plass opprettes 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 til metoden ovenfor:

Tidskompleksitet: Tidskompleksiteten til den gitte koden er O(n), der n er lengden på inndatastrengen. Dette er fordi while-løkken i `isPalindrome`-metoden itererer gjennom halvparten av strengen for å sjekke om det er et palindrom. Siden vi bare sjekker halvparten av strengen, er antall iterasjoner proporsjonalt med n/2, som er O(n).

Plass kompleksitet: Kodens plasskompleksitet er O(1), fordi koden bare bruker en konstant mengde ekstra plass som er uavhengig av inngangsstørrelsen. De eneste variablene som brukes i koden er i, j, str og str2, som hver tar opp en konstant mengde plass. Ingen ekstra plass opprettes i koden.

3. Rekursiv tilnærming for P alindrome-program i Java

Tilnærmingen er veldig enkel. Akkurat som to-peker-tilnærmingen, vil vi sjekke den første og den siste verdien av strengen, men denne gangen vil det være gjennom rekursjon.

innsettingssortering i java

• Vi tar to pekere i som peker til begynnelsen av strengen og j som peker mot slutten av strengen.
• Fortsett å øke i og redusere j mens i
• Sjekk om tegnene på disse pekerne er de samme eller ikke. Vi gjør dette gjennom rekursjon – (i+1, j-1
• Hvis alle tegnene er like på ith og jth indeksen til i>=j betingelsen oppfyller, skriv ut true else false.

Nedenfor er implementeringen av tilnærmingen ovenfor:

// 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 pekerne if (A.charAt(i) != A.charAt(j)) { return false; } // sjekker alt igjen rekursivt returnerer isPalindrome(i + 1, j - 1, A); } public static boolean isPalindrome(String A) { return isPalindrome(0, A.length() - 1, A); } // hovedfunksjon public static void main(String[] args) { // Input string String A = 'geeks'; // Konverter strengen til små bokstaver A = A.toLowerCase(); boolsk str = erPalindrom(A); System.out.println(str); } }>

false>

Kompleksiteten til metoden ovenfor:

Tidskompleksitet: Tidskompleksiteten til den gitte koden er O(n), der n er lengden på inndatastrengen. Dette er fordi `isPalindrome`-funksjonen rekursivt kaller seg for tegnene i posisjonene (i+1, j-1) inntil pekerne i og j krysser hverandre eller tegnene ved pekerne ikke er like. Siden vi sammenligner hvert tegn i strengen nøyaktig én gang, er tidskompleksiteten O(n).

Plass kompleksitet: Romkompleksiteten til koden er O(n), der n er lengden på inndatastrengen. Dette er fordi hvert rekursivt kall oppretter en ny stabelramme som lagrer gjeldende verdier for funksjonsparametere og lokale variabler. I verste fall kan funksjonskallstakken vokse så stor som n/2 (når inngangsstrengen er et palindrom), så romkompleksiteten er O(n).

4. Bruke StringBuilder Approach i Java

I denne tilnærmingen,

konvertering fra dato til streng

• Først tar vi String-inngangen fra brukeren.
• Deretter lager vi Stringbuilder-objektet str1″og lagrer verdien av String i det.
• Reverse()-metoden i Stringbuider gir oss den omvendte strengen. Ee lagre den omvendte strengen i str1.
• Ved hjelp av equals()-metoden sammenligner vi verdiene til strengen, ved hjelp av if and else condition check at strengverdien er lik eller ikke.

Nedenfor er implementeringen av tilnærmingen ovenfor:

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 til koden ovenfor:

Tidskompleksitet: Tidskompleksiteten til koden er O(n), der n igjen er lengden på inndatastrengen str. Den primære faktoren som bidrar til denne tidskompleksiteten er reversering av strengen ved å bruke str1.reverse(). Å snu en streng på denne måten har en tidskompleksitet på O(n), der n er lengden på strengen. Andre operasjoner i koden, for eksempel å lese inndataene og sammenligne strengene, er konstant-tidsoperasjoner og påvirker ikke den totale tidskompleksiteten nevneverdig.

Plass kompleksitet: Romkompleksiteten til den gitte Java-koden er O(n), der n er lengden på inndatastrengen str. Dette er fordi koden bruker en StringBuilder til å lagre en omvendt kopi av inndatastrengen, og plassen som kreves for StringBuilder er proporsjonal med lengden på inndatastrengen.

Henvisning

For å vite mer om Palindrome se Program for strengpalindrom .