πώς να Reverse μια συμβολοσειρά Java χρησιμοποιώντας το Recursion

Σε αυτό το παράδειγμα προγράμματος, θα αντιστρέψουμε μια συμβολοσειρά που έχει εισαχθεί από έναν χρήστη.

Θα δημιουργήσουμε μια συνάρτηση για να αντιστρέψουμε μια συμβολοσειρά. Later Θα το καλούμε αναδρομικά μέχρι να αντιστραφούν όλοι οι χαρακτήρες. Η αναδρομή ταιριάζει σε αυτό το πρόβλημα επειδή μια ανεστραμμένη συμβολοσειρά είναι απλώς η ανεστραμμένη ουρά της συμβολοσειράς με τον αρχικό πρώτο χαρακτήρα κολλημένο στο τέλος, το οποίο είναι το ίδιο πρόβλημα με έναν χαρακτήρα μικρότερο.

Γράψε ένα Java Πρόγραμμα για να Reverse Σπάγγος

Η παρακάτω κλάση δηλώνει την είσοδο στην main(), την παραδίδει στην reverseString() και εκτυπώνει την απάντηση. Δύο κλήσεις println() μέσα στη μέθοδο κάνουν κάθε αναδρομικό βήμα ορατό στην κονσόλα.

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 Παραγωγή:

Κάθε γραμμή της εξόδου είναι μία αναδρομική κλήση. Η ουρά που εκτυπώνεται σε κάθε γραμμή είναι κατά έναν χαρακτήρα μικρότερη από την γραμμή από πάνω της και η τελευταία γραμμή δείχνει το αντίστροφο αποτέλεσμα.

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

Πώς η Αναδρομική Reversal Έργα Βήμα προς Βήμα

Δύο γραμμές φέρουν ολόκληρη τη μέθοδο. Η βασική περίπτωση, if (myStr.isEmpty()), δίνει στην αναδρομή ένα σημείο για να σταματήσει. Η αναδρομική γραμμή, return reverseString(myStr.substring(1)) + myStr.charAt(0), χωρίζει την εργασία σε δύο: substring(1) είναι όλα όσα ακολουθούν τον πρώτο χαρακτήρα, και charAt(0) είναι αυτός ο πρώτος χαρακτήρας, προσαρτημένος μετά το αντίστροφο υπόλοιπο.

Tracεισαγωγή GuruΤο 99 καθιστά σαφή την τάξη. Java ωθεί ένα πλαίσιο για κάθε κλήση πριν συμβεί οποιαδήποτε συνένωση:

Η στοίβα στη συνέχεια ξετυλίγεται από κάτω προς τα πάνω και κάθε πλαίσιο προσθέτει τον αποθηκευμένο χαρακτήρα του: η κενή συμβολοσειρά γίνεται 9, μετά 99, μετά 99u, 99ur, 99uru και τέλος 99uruG. Επειδή Java Οι συμβολοσειρές είναι αμετάβλητες, καμία από αυτές τις ενδιάμεσες τιμές δεν αντικαθιστά την προηγούμενη — κάθε συνένωση εκχωρεί ένα νέο αντικείμενο String.

Δύο λεπτομέρειες στην έξοδο της κονσόλας αξίζει να αναφερθούν. Η έκτη γραμμή δεν τελειώνει με τίποτα μετά την άνω και κάτω τελεία, επειδή η substring(1) σε μια συμβολοσειρά ενός χαρακτήρα επιστρέφει την κενή συμβολοσειρά αντί για null. Το μήνυμα που ακολουθεί αναφέρει "String in now Empty" στο αρχικό πρόγραμμα. Η διατύπωση είναι τυπογραφικό λάθος για το "String is now empty" και έχει παραμείνει ανέπαφη, επομένως ο κώδικας και η παραπάνω έξοδος εξακολουθούν να ταιριάζουν γραμμή προς γραμμή.

Άλλοι τρόποι για να Reverse μια συμβολοσειρά Java

Η αναδρομή είναι ο πιο σαφής τρόπος για να δείτε η αντιστροφή συμβαίνει, αλλά σπάνια συμβαίνει με τον τρόπο που το κάνει ο κώδικας παραγωγής. Τρεις εναλλακτικές λύσεις καλύπτουν σχεδόν κάθε πραγματική περίπτωση.

1. StringBuilder.reverse() είναι η συντομότερη και η ταχύτερη. Η κλάση φέρει ενσωματωμένη μια μέθοδο reverse(), επομένως ολόκληρη η εργασία χωράει σε μία γραμμή:

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

2. Ένας βρόχος for με charAt() οδηγεί τη συμβολοσειρά προς τα πίσω από τον τελευταίο δείκτη στο μηδέν. Οι συνεντευξιαστές συχνά ζητούν αυτήν την εκδοχή επειδή δείχνει τη λογική αντί να την αναθέτει σε κάποιον άλλο:

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

3. Μια εναλλαγή δύο δεικτών με την συνάρτηση toCharArray() μετατρέπει τη συμβολοσειρά σε έναν πίνακα char και, στη συνέχεια, ανταλλάσσει τους εξωτερικούς χαρακτήρες προς τα μέσα μέχρι οι δείκτες να συναντηθούν στη μέση:

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

Η ίδια τεχνική πίνακα αντιστρέφει μια αριθμητική ακολουθία ή οποιαδήποτε άλλη διατεταγμένη συλλογή, γι' αυτό και εμφανίζεται σε Java παράταξη ασκήσεις τόσο συχνά όσο και στις χορδές.

Χρονική και χωρική πολυπλοκότητα κάθε προσέγγισης

Οι τέσσερις εκδόσεις δεν κοστίζουν το ίδιο. Και οι δύο τετραγωνικές καταχωρήσεις παρακάτω έχουν έναν κοινό λόγο: δημιουργούν μια ολοκαίνουργια συμβολοσειρά σε κάθε βήμα και η αντιγραφή n χαρακτήρων n φορές ισούται με n τετραγωνική εργασία.

Επιλέξτε την αναδρομική έκδοση για να μάθετε ή να δείξετε πώς συμπεριφέρεται η στοίβα κλήσεων, την έκδοση char-array όταν ένας συνεντευξιαστής ζητά τη λογική χειροκίνητα και την StringBuilder.reverse() σε οτιδήποτε αποστέλλεται. Η ίδια αντιστάθμιση μεταξύ μιας λύσης διδασκαλίας και μιας λύσης παραγωγής εμφανίζεται σε όλες τις κλασικές ασκήσεις, από τύπος φυσαλίδων και την Σειρά Fibonacci προς την έλεγχοι πρώτων αριθμών; αξίζει να εξασκηθείτε σε κάθε ένα Java και προς τους δύο τρόπους.

Συχνές Ερωτήσεις