Hur man Reverse en sträng i Java med hjälp av rekursion

⚡ Smart sammanfattning

Revatt slänga in en sträng Java Med rekursion fungerar det genom att skala bort det första tecknet, återställa det som blir kvar och lägga till det första tecknet i slutet. En tom sträng stoppar anropen och avvecklar stacken.

  • 🔘 Grundfall: Metoden returnerar direkt när isEmpty() rapporterar att inget finns kvar att reversera.
  • ☑️ Rekursivt steg: substring(1) tar bort det första tecknet och charAt(0) sätter tillbaka det efter den omvända resten.
  • ✅ Oföränderlighet: Varje anrop producerar ett nytt String-objekt, eftersom en Java Strängen kan aldrig redigeras på plats.
  • 🧪 Trace: Guru99 blir 99uruG efter sju anrop, ett för varje tecken plus det tomma basfallet.
  • 🛠️ Snabbare alternativ: StringBuilder.reverse() och ett tvåpekarsbyte till CharArray() avslutas båda i ett enda svep.
  • 📌 Kostnad: Rekursion med substring() körs i kvadratisk tid och innehåller en stackframe per tecken.

Java program som reverserar en sträng med hjälp av en rekursiv metod

I detta exempelprogram kommer vi att vända en sträng som angetts av en användare.

Vi kommer att skapa en funktion för att vända en sträng. Later Vi kommer att kalla det rekursivt tills alla tecken är omvända. Rekursion passar detta problem eftersom en omvänd sträng helt enkelt är den omvända svansen av strängen med det ursprungliga första tecknet fast i slutet, vilket är samma problem ett tecken mindre.

Skriv en Java Program till Reverse Sträng

Klassen nedan deklarerar indata i main(), skickar den till reverseString() och skriver ut det som kommer tillbaka. Två println()-anrop inuti metoden gör varje rekursivt steg synligt i konsolen.

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 Produktion:

Varje rad i utdata är ett rekursivt anrop. Svansen som skrivs ut på varje rad är ett tecken kortare än raden ovanför, och den sista raden visar det omvända resultatet.

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

Hur den rekursiva Reversal Works steg för steg

Två rader bär hela metoden. Basfallet, if (myStr.isEmpty()), ger rekursionen någonstans att stoppa. Den rekursiva raden, return reverseString(myStr.substring(1)) + myStr.charAt(0), delar upp arbetet i två delar: substring(1) är allt efter det första tecknet, och charAt(0) är det första tecknet, tillagt. efter den omvända resten.

Tracinmatningen Guru99 gör ordningen tydlig. Java skickar en ram för varje anrop innan någon sammankoppling sker:

Ring uppminStrVidarebefordrad till nästa samtalUttryck väntar på att bli klart
1Guru99uru99omvändSträng("uru99") + G
2uru99ru99omvändSträng("ru99") + u
3ru99u99omvändSträng("u99") + r
4u9999omvändSträng("99") + u
5999omvändSträng("9") + 9
69(tömma)omvändSträng("") + 9
7(tömma)basfallet uppnåttreturnerar den tomma strängen

Stacken rullas sedan ut nerifrån och upp, och varje ram lägger till sitt sparade tecken: den tomma strängen blir 9, sedan 99, sedan 99u, 99ur, 99uru och slutligen 99uruG. Därför att Java Strängar är oföränderliga, inget av dessa mellanliggande värden skriver över det föregående — varje sammankoppling allokerar ett nytt String-objekt.

Två detaljer i konsolutdata är värda att nämna. Den sjätte raden slutar med ingenting efter kolon, eftersom substring(1) på en enteckenssträng returnerar den tomma strängen snarare än null. Meddelandet som följer lyder "String in now Empty" i det ursprungliga programmet; formuleringen är ett stavfel för "String is now empty" och har lämnats orört så att koden och utdata ovan fortfarande matchar rad för rad.

Andra sätt att Reverse en sträng i Java

Rekursion är det tydligaste sättet att se Omkastningen sker, men det är sällan så produktionskod gör det. Tre alternativ täcker nästan alla verkliga fall.

1. StringBuilder.reverse() är den kortaste och snabbaste. Klassen har en inbyggd reverse()-metod, så hela jobbet får plats på en rad:

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

2. En for-loop med charAt() går strängen bakåt från det senaste indexet till noll. Intervjuare frågar ofta efter den här versionen eftersom den visar logiken istället för att delegera den:

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

3. En tvåpoängsväxling till CharArray() konverterar strängen till en char-array och byter sedan ut de yttersta tecknen inåt tills pekarna möts i mitten:

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);

Samma arrayteknik reverserar en numerisk sekvens eller någon annan ordnad samling, vilket är anledningen till att den dyker upp i Java array övningar lika ofta som i strängövningar.

Tids- och rumskomplexitet för varje tillvägagångssätt

De fyra versionerna kostar inte lika mycket. Båda kvadratiska posterna nedan har en gemensam orsak: de skapar en helt ny sträng i varje steg, och att kopiera n tecken n gånger är n kvadratarbete.

TillvägagångssättTidExtra utrymmeVarför
Rekursion med delsträng()O(n²)O(n²)substring() kopierar de återstående tecknen vid varje anrop, och en stackframe hålls per tecken
för-loop med charAt() och +O(n²)O(n²)Varje sammanfogning allokerar en ny sträng och kopierar allt som hittills samlats in.
StringBuilder.reverse()O (n)O (n)Ett muterbart buffert-, ett pass- och surrogatpar hålls intakta
Två pekare över tillCharArray()O (n)O (n)En arraykopia, sedan n/2 växlingar utan ytterligare allokering

Välj den rekursiva versionen för att lära dig eller demonstrera hur anropsstacken beter sig, char-array-versionen när en intervjuare frågar efter logiken manuellt, och StringBuilder.reverse() i allt som levereras. Samma avvägning mellan en undervisningslösning och en produktionslösning dyker upp i de klassiska övningarna, från bubbelsorter och Fibonacci-serien till primtalkontroller; var och en är värd att öva på Java båda vägarna.

Vanliga frågor

Strängobjekt är oföränderliga, så tecknen inuti ett kan aldrig ändras efter att det skapats. Varje omkastning skapar därför ett nytt objekt. Använd StringBuilder eller en teckenuppsättning när tecknen måste ändras utan att allokera en ny sträng i varje steg.

Det första anropet till isEmpty() kastar ett NullPointerException, eftersom metoden anropas på ingenting. Skydda startpunkten med en null-kontroll som returnerar null eller kastar IllegalArgumentException innan någon rekursion börjar.

Inte tillförlitligt. charAt() fungerar på 16-bitars kodenheter, så ett tecken som lagras som ett surrogatpar delas och den omvända texten visar ersättningsrutor. StringBuilder.reverse() håller ihop surrogatpar, vilket gör det till ett säkrare val för Unicode-text.

StringBuilder, i nästan alla fall. Båda exponerar samma reverse()-metod, men StringBuffer synkroniserar varje samtal, vilket kostar snabbhet. Välj StringBuffer endast när en buffert verkligen delas mellan trådar.

Dela meningen på blanksteg med split(" "), gå sedan den resulterande arrayen från det sista indexet till det första, och lägg till varje ord i en StringBuilder. Tecknen inuti varje ord behåller sin ursprungliga ordning.

En stackram används per tecken, så några tusen tecken är typiskt innan ett StackOverflowError visas. Den exakta gränsen beror på JVM-trådstackens storlek. Varje iterativ version undviker taket helt.

En AI-assistent kan läsa en stack trace.g. peka på ett saknat eller oåtkomligt basfall och förklara i vilken ordning ramar avvecklas. Den utarbetar även kantfallstester för tomma, enteckens- och null-indata. Verifiera resonemanget mot en verklig körning.

Ja. Copilot brukar vanligtvis slutföra en hel omvänd metod enbart från signaturen, och erbjuder ofta StringBuilder-formuläret först. Kontrollera grundfallet och komplexiteten, eftersom det kortaste förslaget inte alltid är den version som en övning begär.

Sammanfatta detta inlägg med: