Come Reverse una stringa in Java utilizzando la ricorsione

In questo programma esempio, invertiremo una stringa inserita da un utente.

Creeremo una funzione per invertire una stringa. Later Lo richiameremo ricorsivamente finché tutti i caratteri non saranno invertiti. La ricorsione si adatta a questo problema perché una stringa invertita è semplicemente la coda invertita della stringa con il primo carattere originale attaccato alla fine, che è lo stesso problema con un carattere in meno.

Scrivi a Java Programma per Reverse Corda

La classe seguente dichiara l'input nel metodo main(), lo passa al metodo reverseString() e stampa il risultato. Due chiamate a println() all'interno del metodo rendono visibile nella console ogni passaggio ricorsivo.

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

Ogni riga dell'output rappresenta una chiamata ricorsiva. La parte finale stampata su ogni riga è più corta di un carattere rispetto alla riga precedente, e l'ultima riga mostra il risultato invertito.

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

Come il ricorsivo RevOpere universali passo dopo passo

Due righe contengono l'intero metodo. Il caso base, if (myStr.isEmpty()), fornisce alla ricorsione un punto in cui fermarsi. La riga ricorsiva, return reverseString(myStr.substring(1)) + myStr.charAt(0), divide il lavoro in due: substring(1) è tutto ciò che segue il primo carattere e charAt(0) è quel primo carattere, aggiunto dopo il resto invertito.

Tracl'input GuruIl numero 99 chiarisce l'ordine. Java invia un frame per ogni chiamata prima che avvenga qualsiasi concatenazione:

Lo stack si srotola quindi dal basso verso l'alto e ogni frame aggiunge il suo carattere salvato: la stringa vuota diventa 9, poi 99, poi 99u, 99ur, 99uru e infine 99uruG. Perché Java Le stringhe sono immutabili, nessuno di questi valori intermedi sovrascrive quello precedente: ogni concatenazione alloca un nuovo oggetto String.

Due dettagli nell'output della console meritano di essere menzionati. La sesta riga termina senza nulla dopo i due punti, perché la funzione substring(1) su una stringa di un solo carattere restituisce la stringa vuota anziché null. Il messaggio che segue nel programma originale recita "String in now Empty"; la formulazione è un errore di battitura per "String is now empty" ed è stata lasciata invariata in modo che il codice e l'output sopra riportato corrispondano ancora riga per riga.

Altri modi per Reverse una stringa in Java

La ricorsione è il modo più chiaro per vedere L'inversione può avvenire, ma raramente avviene nel modo in cui il codice di produzione la gestisce. Tre alternative coprono quasi tutti i casi reali.

1. StringBuilder.reverse() è la più breve e la più veloce. La classe include un metodo reverse() integrato, quindi l'intera operazione sta in una sola riga:

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

2. Un ciclo for con charAt() Percorre la stringa a ritroso dall'ultimo indice fino a zero. I selezionatori spesso richiedono questa versione perché mostra la logica invece di delegarla:

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

3. Uno scambio di due puntatori su toCharArray() converte la stringa in un array di caratteri, quindi scambia i caratteri più esterni con quelli più interni finché i puntatori non si incontrano al centro:

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

La stessa tecnica di array inverte una sequenza numerica o qualsiasi altra collezione ordinata, motivo per cui compare in Java schieramento esercizi con la stessa frequenza di quelli con la corda.

Complessità temporale e spaziale di ciascun approccio.

Le quattro versioni non hanno lo stesso costo. Entrambe le voci quadratiche qui sotto hanno una causa comune: creano una stringa completamente nuova a ogni passaggio, e copiare n caratteri n volte richiede un lavoro pari a n al quadrato.

Scegli la versione ricorsiva per imparare o per dimostrare come si comporta lo stack di chiamate, la versione con array di caratteri quando un intervistatore chiede la logica a mano e StringBuilder.reverse() in qualsiasi versione distribuita. Lo stesso compromesso tra una soluzione didattica e una di produzione si presenta in tutti gli esercizi classici, da ordinamento a bolle e Serie di Fibonacci a controlli dei numeri primi; vale la pena praticare ciascuno di essi Java in entrambi i sensi.

DOMANDE FREQUENTI