kuidas Reverse string sees Java kasutades rekursiooni

Selles näidisprogrammis pöörame kasutaja sisestatud stringi ümber.

Loome funktsiooni stringi ümberpööramiseks. Later Me nimetame seda rekursiivselt seni, kuni kõik märgid on vastupidised. Rekursioon sobib sellele probleemile, sest vastupidine string on lihtsalt stringi vastupidine saba, mille lõppu on kleebitud algne esimene märk, mis on sama probleem ühe märgi võrra väiksemana.

Kirjuta Java Programmeerida Reverse nöör

Allolev klass deklareerib sisendi funktsioonis main(), annab selle funktsioonile reverseString() ja kuvab vastuse. Kaks meetodi sees olevat println() käsku muudavad iga rekursiivse sammu konsoolis nähtavaks.

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 Väljund:

Iga väljundi rida on üks rekursiivne kutse. Igal real trükitud saba on ühe märgi võrra lühem kui ülemine rida ja viimane rida näitab vastupidist tulemust.

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

Kuidas rekursiivne Reversal töötab samm-sammult

Kogu meetod sisaldab kahte rida. Baasjuhul, kui (myStr.isEmpty()), antakse rekursioonile peatumiskoht. Rekursiivne rida, return reverseString(myStr.substring(1)) + myStr.charAt(0), jagab töö kaheks: substring(1) on kõik pärast esimest märki ja charAt(0) on see esimene märk, millele on lisatud. pärast vastupidine jääk.

Tracsisendi sisestamine Guru99 teeb järjekorra selgeks. Java lükkab iga kutse kohta ühe kaadri enne liitmist:

Seejärel harutatakse pinu alt ülespoole lahti ja iga kaader lisab oma salvestatud märgi: tühjast stringist saab 9, seejärel 99, siis 99u, 99ur, 99uru ja lõpuks 99uruG. Sest Java stringid on muutumatud, ükski neist vaheväärtustest ei kirjuta eelmist üle — iga liitmine eraldab uue String-objekti.

Konsooli väljundis väärivad nimetamist kaks detaili. Kuues rida lõpeb pärast koolonit tühja reaga, kuna ühetähemärgilise stringi substring(1) tagastab tühja stringi, mitte nulli. Järgnev teade on algses programmis „String on nüüd tühi”; sõnastus on „String on nüüd tühi” asemel trükiviga ja seda on muutmata, seega ülaltoodud kood ja väljund vastavad endiselt rida-realt.

Muud viisid Reverse string sees Java

Rekursioon on kõige selgem viis vaata Pöördumine toimub, kuid harva tehakse seda nii, nagu tootmiskood seda teeb. Kolm alternatiivi hõlmavad peaaegu iga reaalset juhtumit.

1. StringBuilder.reverse() on lühim ja kiireim. Klassil on sisseehitatud reverse() meetod, seega mahub kogu töö ühele reale:

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

2. A for-tsükkel funktsiooniga charAt() käib stringis tagasi viimasest indeksist nullini. Intervjueerijad küsivad sageli seda versiooni, sest see näitab loogikat selle delegeerimise asemel:

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

3. Kahe osutiga objekti vahetus funktsioonile CharArray() teisendab stringi char-massiiviks ja seejärel vahetab äärmised märgid sissepoole, kuni pointerid kohtuvad keskel:

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

Sama massiivitehnika pöörab numbrilise jada või mis tahes muu järjestatud kogumi ümber, mistõttu see kuvatakse Java massiivi harjutusi sama tihti kui keelpillidega harjutusi.

Iga lähenemisviisi ajaline ja ruumiline keerukus

Need neli versiooni ei maksa sama palju. Mõlemal alloleval ruutülesandel on üks ja sama põhjus: need loovad igal sammul täiesti uue stringi ja n tähemärgi n korda kopeerimine on n ruudus töö.

Valige rekursiivne versioon õppimiseks või väljakutsete pinu käitumise demonstreerimiseks, tähestikuline massiiviversioon, kui intervjueerija küsib loogikat käsitsi, ja StringBuilder.reverse() kõiges, mis tarnitakse. Sama kompromiss õpetamislahenduse ja tootmislahenduse vahel ilmneb kõigis klassikalistes harjutustes, alates mulli sorteerimine ja Fibonacci seeria et algarvude kontrollidigaüks neist on harjutamist väärt; Java mõlemas suunas.

KKK