Hvordan man Reverse en streng i Java ved hjælp af rekursion

I dette eksempelprogram vil vi vende en streng indtastet af en bruger.

Vi vil oprette en funktion til at vende en streng. Later Vi kalder det rekursivt, indtil alle tegn er omvendte. Rekursion passer til dette problem, fordi en omvendt streng simpelthen er den omvendte hale af strengen med det oprindelige første tegn fastgjort for enden, hvilket er det samme problem et tegn mindre.

Skriv en Java Program til Reverse String

Klassen nedenfor deklarerer inputtet i main(), sender det til reverseString() og udskriver det, der kommer tilbage. To println()-kald i metoden gør hvert rekursive trin synligt i konsollen.

package com.guru99;
 
public class ReverseString {
 
	public static void main(String[] args) {
 
 
		String myStr = "Guru99";
 
 
		//create Method and pass and input parameter string 
		String reversed = reverseString(myStr);
		System.out.println("The reversed string is: " + reversed);
		
	}
 
 
	//Method take string parameter and check string is empty or not
	public static String reverseString(String myStr)
	{
		if (myStr.isEmpty()){
		 System.out.println("String in now Empty");	
		 return myStr;
		}
		//Calling Function Recursively
		System.out.println("String to be passed in Recursive Function: "+myStr.substring(1));
		return reverseString(myStr.substring(1)) + myStr.charAt(0);
	}
 
}

Code Output:

Hver linje i outputtet er ét rekursivt kald. Halen, der er trykt på hver linje, er et tegn kortere end linjen ovenover, og den sidste linje viser det omvendte resultat.

String to be passed in Recursive Function: uru99
String to be passed in Recursive Function: ru99
String to be passed in Recursive Function: u99
String to be passed in Recursive Function: 99
String to be passed in Recursive Function: 9
String to be passed in Recursive Function: 
String in now Empty
The reversed string is: 99uruG

Hvordan den rekursive Reversal Works Trin for Trin

To linjer bærer hele metoden. Basistilfældet, if (myStr.isEmpty()), giver rekursionen et sted at stoppe. Den rekursive linje, return reverseString(myStr.substring(1)) + myStr.charAt(0), deler arbejdet i to: substring(1) er alt efter det første tegn, og charAt(0) er det første tegn, tilføjet. efter den omvendte rest.

Tracinputtet Guru99 gør rækkefølgen klar. Java skubber én frame for hvert kald, før der sker nogen sammenkædning:

Stakken rulles derefter ud fra bunden og opad, og hver frame tilføjer sit gemte tegn: den tomme streng bliver 9, derefter 99, derefter 99u, 99ur, 99uru og til sidst 99uruG. Fordi Java Strenge er uforanderlige, ingen af ​​disse mellemliggende værdier overskriver den foregående — hver sammenkædning allokerer et nyt String-objekt.

To detaljer i konsoloutputtet er værd at nævne. Den sjette linje slutter med ingenting efter kolon, fordi substring(1) på en streng på et tegn returnerer den tomme streng i stedet for null. Den efterfølgende besked lyder "String in now Empty" i det originale program; formuleringen er en slåfejl for "String is now empty" og er blevet ladt uændret, så koden og outputtet ovenfor stadig matcher linje for linje.

Andre måder at Reverse en streng i Java

Rekursion er den klareste måde at se omvendingen sker, men det er sjældent den måde, produktionskoden gør det på. Tre alternativer dækker næsten alle virkelige tilfælde.

1. StringBuilder.reverse() er den korteste og hurtigste. Klassen har en indbygget reverse() metode, så hele jobbet passer på én linje:

String reversed = new StringBuilder(myStr).reverse().toString();

2. En for-løkke med charAt() går strengen baglæns fra det sidste indeks til nul. Interviewere beder ofte om denne version, fordi den viser logikken i stedet for at delegere den:

String reversed = "";
for (int i = myStr.length() - 1; i >= 0; i--) {
    reversed = reversed + myStr.charAt(i);
}

3. En to-pointer ombytning til CharArray() konverterer strengen til et char-array og bytter derefter de yderste tegn indad, indtil pointerne mødes i midten:

char[] chars = myStr.toCharArray();
int left = 0;
int right = chars.length - 1;
while (left < right) {
    char temp = chars[left];
    chars[left] = chars[right];
    chars[right] = temp;
    left++;
    right--;
}
String reversed = new String(chars);

Den samme arrayteknik vender en numerisk sekvens eller enhver anden ordnet samling om, hvilket er grunden til, at den optræder i Java matrix øvelser lige så ofte som i strengeøvelser.

Tids- og rumkompleksitet for hver tilgang

De fire versioner koster ikke det samme. Begge kvadratiske poster nedenfor deler én årsag: de opretter en helt ny streng i hvert trin, og at kopiere n tegn n gange er n kvadratisk arbejde.

Vælg den rekursive version for at lære eller demonstrere, hvordan call stacken opfører sig, char-array-versionen, når en interviewer beder om logikken manuelt, og StringBuilder.reverse() i alt, der sendes. Den samme afvejning mellem en undervisningsløsning og en produktionsløsning ses på tværs af de klassiske øvelser, fra boble sortering og Fibonacci-serien til primtalkontroller; hver enkelt er værd at øve sig i Java begge veje.

Ofte Stillede Spørgsmål