Hoe werkt het? Reverse een String in Java met behulp van recursie

In dit voorbeeldprogramma keren we een string om die door een gebruiker is ingevoerd.

We zullen een functie maken om een ​​string om te keren. Later We roepen de functie recursief aan totdat alle tekens zijn omgekeerd. Recursie is geschikt voor dit probleem omdat een omgekeerde string simpelweg het omgekeerde deel van de string is, met het oorspronkelijke eerste teken eraan vastgeplakt. Dit is in feite hetzelfde probleem, maar dan met één teken minder.

Schrijf een Java Programmeren naar Reverse Draad

De onderstaande klasse declareert de invoer in main(), geeft deze door aan reverseString() en print de uitvoer. Twee println()-aanroepen binnen de methode maken elke recursieve stap zichtbaar in de console.

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:

Elke regel van de uitvoer is een recursieve aanroep. Het laatste teken op elke regel is één teken korter dan de regel erboven, en de laatste regel toont het omgekeerde resultaat.

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

Hoe de recursieve RevErsal-werken stap voor stap

De hele methode bestaat uit twee regels. De basiscase, `if (myStr.isEmpty())`, geeft de recursie een stoppunt. De recursieve regel, `return reverseString(myStr.substring(1)) + myStr.charAt(0)`, splitst het werk in tweeën: `substring(1)` is alles na het eerste teken, en `charAt(0)` is dat eerste teken, eraan toegevoegd. na het omgekeerde restant.

Tracde invoer Guru99 maakt de volgorde duidelijk. Java Er wordt één frame per oproep verzonden voordat er enige samenvoeging plaatsvindt:

De stapel wordt vervolgens van onder naar boven afgewikkeld, en elk frame voegt het opgeslagen teken toe: de lege tekenreeks wordt 9, dan 99, dan 99u, 99ur, 99uru, en uiteindelijk 99uruG. Omdat Java Strings zijn onveranderlijk; geen van deze tussenliggende waarden overschrijft de vorige — elke samenvoeging creëert een nieuw String-object.

Twee details in de console-uitvoer zijn het vermelden waard. De zesde regel eindigt zonder iets na de dubbele punt, omdat substring(1) op een tekenreeks van één teken een lege tekenreeks retourneert in plaats van null. Het bericht dat volgt luidt "String in now Empty" in het originele programma; de formulering is een typefout voor "String is now empty" en is ongewijzigd gelaten, zodat de code en de bovenstaande uitvoer nog steeds regel voor regel overeenkomen.

Andere manieren Reverse een String in Java

Recursie is de duidelijkste manier om zien De omkering vindt wel plaats, maar zelden op de manier waarop de productiecode dat doet. Drie alternatieven dekken vrijwel elk praktijkgeval.

1. StringBuilder.reverse() is de kortste en snelste. De klasse heeft een ingebouwde `reverse()`-methode, waardoor de hele taak op één regel past:

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

2. Een for-lus met charAt() Doorloopt de tekenreeks achterwaarts vanaf de laatste index tot nul. Interviewers vragen vaak naar deze versie omdat die de logica laat zien in plaats van deze uit te besteden:

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

3. Een tweepointerwissel bij toCharArray() converteert de tekenreeks naar een tekenreeksarray en verwisselt vervolgens de buitenste tekens van binnen naar buiten totdat de pointers elkaar in het midden ontmoeten:

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

Dezelfde arraytechniek keert een numerieke reeks of een andere geordende verzameling om, vandaar dat deze techniek opduikt in... Java reeks Net zo vaak oefenen als bij strijkers.

Tijd- en ruimtecomplexiteit van elke aanpak

De vier versies kosten niet hetzelfde. Beide kwadratische termen hieronder hebben één gemeenschappelijke oorzaak: ze creëren bij elke stap een volledig nieuwe tekenreeks, en het kopiëren van n tekens n keer is n kwadratisch werk.

Kies de recursieve versie om te leren of te demonstreren hoe de aanroepstack werkt, de versie met tekenreeksen wanneer een interviewer vraagt ​​om de logica handmatig uit te voeren, en StringBuilder.reverse() in alles wat wordt uitgebracht. Dezelfde afweging tussen een leeroplossing en een productieoplossing komt terug in de klassieke oefeningen, van bellen sorteren en Fibonacci-reeks naar priemgetalcontroles; elk ervan is de moeite waard om te oefenen Java beide kanten op.

Veelgestelde vragen