jak na to Reverse řetězec v Java pomocí rekurze

V tomto vzorovém programu obrátíme řetězec zadaný uživatelem.

Vytvoříme funkci pro obrácení řetězce. Later Budeme to volat rekurzivně, dokud nebudou všechny znaky obráceny. Rekurze se k tomuto problému hodí, protože obrácený řetězec je jednoduše obrácený konec řetězce s původním prvním znakem na konci, což je stejný problém, jen o jeden znak menší.

Napsat Java Programovat do Reverse Řetězec

Níže uvedená třída deklaruje vstup v main(), předá jej reverseString() a vypíše vrácenou hodnotu. Dvě volání println() uvnitř metody zviditelní každý rekurzivní krok v konzoli.

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ýstup:

Každý řádek výstupu je jedno rekurzivní volání. Konec vytištěný na každém řádku je o jeden znak kratší než řádek nad ním a poslední řádek zobrazuje obrácený výsledek.

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

Jak rekurzivní Reversal funguje krok za krokem

Celou metodu nesou dva řádky. Základní případ, if (myStr.isEmpty()), určuje místo, kde se má rekurze zastavit. Rekurzivní řádek return reverseString(myStr.substring(1)) + myStr.charAt(0) rozděluje práci na dvě části: substring(1) je vše za prvním znakem a charAt(0) je tento první znak, připojený k po obrácený zbytek.

Traczadávání vstupu Guru99 objasňuje pořadí. Java vloží jeden rámec pro každé volání, než dojde k jakémukoli zřetězení:

Zásobník se poté odvíjí zdola nahoru a každý rámec připojuje svůj uložený znak: prázdný řetězec se stane 9, poté 99, pak 99u, 99ur, 99uru a nakonec 99uruG. Protože Java Řetězce jsou neměnné, žádná z těchto mezilehlých hodnot nepřepíše předchozí – každé zřetězení alokuje nový objekt String.

Za zmínku stojí dva detaily ve výstupu do konzole. Šestý řádek končí za dvojtečkou ničím, protože substring(1) u jednoznakového řetězce vrací prázdný řetězec, nikoli hodnotu null. Následující zpráva v původním programu zní „String in now Empty“ (Řetězec je nyní prázdný); formulace „String is now empty“ (Řetězec je nyní prázdný) je překlepem a zůstala nedotčena, takže kód a výstup výše se stále shodují řádek od řádku.

Jiné způsoby Reverse řetězec v Java

Rekurze je nejjasnější způsob, jak vidět K obrácení dochází, ale v produkčním kódu se to stává jen zřídka. Tři alternativy pokrývají téměř každý reálný případ.

1. StringBuilder.reverse() je nejkratší a nejrychlejší. Třída má vestavěnou metodu reverse(), takže se celá úloha vejde na jeden řádek:

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

2. Cyklus for s funkcí charAt() Prochází řetězec pozpátku od posledního indexu k nule. Tazatelé se často ptají na tuto verzi, protože ukazuje logiku, místo aby ji delegovala:

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

3. Dvouukazatelová swapovací funkce typu toCharArray() převede řetězec na pole znaků a poté vymění nejvzdálenější znaky směrem dovnitř, dokud se ukazatele nesetkají uprostřed:

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

Stejná technika pole obrací číselnou posloupnost nebo jakoukoli jinou uspořádanou kolekci, a proto se objevuje v Java řada cvičení stejně často jako u strunných nástrojů.

Časová a prostorová složitost každého přístupu

Čtyři verze se liší cenou. Oba níže uvedené kvadratické členy mají jeden společný důvod: v každém kroku vytvářejí zcela nový řetězec a kopírování n znaků n-krát je n na druhou.

Vyberte rekurzivní verzi pro naučení nebo demonstraci chování zásobníku volání, verzi s polem znaků, když se tazatel ručně zeptá na logiku, a StringBuilder.reverse() v čemkoli, co je součástí dodávky. Stejný kompromis mezi výukovým řešením a produkčním řešením se projevuje v klasických cvičeních, od bublinové řazení a Fibonacciho řada na kontroly prvočíselkaždý z nich stojí za procvičení Java oběma směry.

Nejčastější dotazy