Hvordan Reverse en streng i Java ved hjelp av rekursjon

I dette eksempelprogrammet vil vi reversere en streng som er skrevet inn av en bruker.

Vi vil lage en funksjon for å reversere en streng. Later Vi kaller det rekursivt til alle tegnene er reversert. Rekursjon passer til dette problemet fordi en reversert streng ganske enkelt er den reverserte halen av strengen med det opprinnelige første tegnet fast på enden, som er det samme problemet ett tegn mindre.

Skriv en Java Program til Reverse String

Klassen nedenfor deklarerer inputen i main(), gir den til reverseString(), og skriver ut det som kommer tilbake. To println()-kall inne i metoden gjør hvert rekursive trinn synlig 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 Utgang:

Hver linje i utdataene er ett rekursivt kall. Halen som er trykt på hver linje er ett tegn kortere enn linjen over, og den siste linjen viser det omvendte 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

Hvordan den rekursive Reversal Works trinn for trinn

To linjer bærer hele metoden. Basistilfellet, if (myStr.isEmpty()), gir rekursjonen et sted å stoppe. Den rekursive linjen, return reverseString(myStr.substring(1)) + myStr.charAt(0), deler arbeidet i to: substring(1) er alt etter det første tegnet, og charAt(0) er det første tegnet, lagt til. etter den omvendte resten.

Tracinnspillingen Guru99 gjør rekkefølgen tydelig. Java skyver én ramme for hvert kall før noen sammenkobling skjer:

Stakken rulles deretter ut nedenfra og opp, og hver ramme legger til sitt lagrede tegn: den tomme strengen blir 9, deretter 99, deretter 99u, 99ur, 99uru, og til slutt 99uruG. Fordi Java Strenger er uforanderlige, ingen av disse mellomverdiene overskriver den forrige – hver sammenkobling tildeler et nytt String-objekt.

To detaljer i konsollutdataene er verdt å nevne. Den sjette linjen slutter med ingenting etter kolon, fordi substring(1) på en streng med ett tegn returnerer den tomme strengen i stedet for null. Meldingen som følger lyder «String in now Empty» i det opprinnelige programmet; formuleringen er en skrivefeil for «String is now empty» og har blitt latt urørt, slik at koden og utdataene ovenfor fortsatt samsvarer linje for linje.

Andre måter å Reverse en streng i Java

Rekursjon er den klareste måten å se reverseringen skjer, men det er sjelden slik produksjonskoden gjør det. Tre alternativer dekker nesten alle reelle tilfeller.

1. StringBuilder.reverse() er den korteste og raskeste. Klassen har en innebygd reverse()-metode, slik at hele jobben får plass på én linje:

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

2. En for-løkke med charAt() går strengen bakover fra siste indeks til null. Intervjuere ber ofte om denne versjonen fordi den viser logikken i stedet for å delegere den:

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

3. En to-poengs bytte over til CharArray() konverterer strengen til en char-array, og bytter deretter de ytterste tegnene innover til pekerne møtes 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 arrayteknikken reverserer en numerisk sekvens eller en hvilken som helst annen ordnet samling, og det er derfor den dukker opp i Java matrise øvelser like ofte som i strengøvelser.

Tids- og romkompleksiteten til hver tilnærming

De fire versjonene koster ikke det samme. Begge de kvadratiske oppføringene nedenfor deler én grunn: de oppretter en helt ny streng i hvert trinn, og å kopiere n tegn n ganger er n kvadratisk arbeid.

Velg den rekursive versjonen for å lære eller demonstrere hvordan kallstakken oppfører seg, char-array-versjonen når en intervjuer ber om logikken manuelt, og StringBuilder.reverse() i alt som sendes. Den samme avveiningen mellom en undervisningsløsning og en produksjonsløsning dukker opp på tvers av de klassiske øvelsene, fra boblesortering og Fibonacci-serien til primtallssjekker; hver enkelt er verdt å øve på Java begge veier.

Spørsmål og svar