wake-up-neo.com

Was ist der beste Weg, um eine Zeichenfolge in Java rekursiv umzukehren?

Ich habe heute mit Rekursion herumgespielt. Oft ist eine Programmiertechnik nicht ausreichend.

Ich wollte eine Zeichenfolge rekursiv umkehren. Folgendes habe ich mir ausgedacht:

//A method to reverse a string using recursion
    public String reverseString(String s){
        char c = s.charAt(s.length()-1);
        if(s.length() == 1) return Character.toString(c);   

        return c + reverseString(s.substring(0,s.length()-1));
    }

Meine Frage: Gibt es einen besseren Weg in Java?

24
binarycreations

Am besten verwenden Sie keine Rekursion. Diese Dinge werden normalerweise verwendet, um den Schülern das Rekursionskonzept zu vermitteln, nicht jedoch die bewährten Methoden. So wie du es machst, ist es gut. Verwenden Sie einfach keine Rekursion in Java für solche Dinge in realen Apps;)

PS. Abgesehen von dem, was ich gerade gesagt habe, würde ich "" als Basisfall meiner rekursiven Funktion wählen:

public String reverseString(String s){
    if (s.length() == 0) 
         return s;

    return reverseString(s.substring(1)) + s.charAt(0);
}
50
Mehrdad Afshari

Wenn Sie dies tun möchten, möchten Sie ein Zeichen-Array verwenden, da ein String unveränderlich ist und Sie Strings überall kopieren möchten, wenn Sie dies auf diese Weise tun.

Dies ist ungeprüft und ein ganzer Bewusstseinsstrom. Es hat wahrscheinlich irgendwo einen OB1. Und sehr nicht Java.

public String reverseString(String s)
  {
  char[] cstr = s.getChars();
  reverseCStr(cstr, 0, s.length - 1);

  return new String(cstr);
  }

/**
 * Reverse a character array in place.
 */
private void reverseCStr(char[] a, int s, int e)
  {
  // This is the middle of the array; we're done.
  if (e - s <= 0)
    return;

  char t = a[s];
  a[s] = a[e];
  a[e] = t;
  reverseCStr(a, s + 1, e - 1);
  }
9
Adam Jaskiewicz

Sie wollen nicht zu tief nisten. Teilen und Erobern ist der Weg zu gehen. Reduziert auch die Gesamtgröße temporärer Zeichenfolgen und ist für die Parallelisierung geeignet.

public static String reverseString(String str) {
    int len = str.length();
    return len<=1 ? str : (
        reverseString(str.substring(len/2))+
        reverseString(str.substring(0, len/2))
    );
}

(Nicht getestet - Dies ist Stackoverflow.)

String.concat anstelle von + würde die Leistung auf Kosten der Klarheit verbessern.

Edit: Nur zum Spaß, eine rekursive Version des naiven Algorithmus.

public static String reverseString(String str) {
    return reverseString("", str);
}
private static String reverseString(String reversed, String forward) {
    return forward.equals("") ? reversed : (
         reverseString(reversed+forward.charAt(0), forward.substring(1)) 
    );
}

Die korrekte Handhabung von Ersatzpaaren bleibt dem interessierten Leser überlassen.

hier ist meine rekursive Umkehrfunktion, die gut funktioniert

public static String rev(String instr){
    if(instr.length()<=1){
        return instr;
    } else {
       return (instr.charAt(instr.length()-1)+rev(instr.substring(0,instr.length()-1)) );
    }       
}
3
senthil

Hier ist eine rekursive Methode, die StringBuilder verwendet (was generell empfohlen wird, um Strings zu manipulieren).

public String reverseString(String s_) {
    StringBuilder r = new StringBuilder();
    StringBuilder s = new StringBuilder(s_);
    r = reverseStringHelper(r, s);
    return r.toString();
}
private StringBuilder reverseStringHelper(StringBuilder r, StringBuilder s) {
    if (s.length() == 0)
        return r;
    else
        return reverseStringHelper(r.append(s.charAt(0)), s.deleteCharAt(0));
}

Ungetestet habe ich mich seit Jahren nicht mit Java befasst, aber das sollte ungefähr stimmen.

2
ephemient

Wenn Sie echten Code schreiben (keine Rekursion lernen), verwenden Sie die reverse () - Methode von StringBuilder. Das Java Tutorial gibt dieses Beispiel:

String palindrome = "Dot saw I was Tod";   
StringBuilder sb = new StringBuilder(palindrome);
sb.reverse();  // reverse it
System.out.println(sb);
2
Jim Ferrans

In Java ist die String-Verkettung komplexer, als es aussieht, da der String unveränderlich ist. 

Bei jeder Verkettung wird eine neue Zeichenfolge erstellt, die den Inhalt der ursprünglichen Zeichenfolge kopiert. Dies führt zu einer linearen Komplexität O(n) wobei n die Länge der Zeichenfolge ist, also für m solche Operationen es ist O (m * n) , wir können sagen, dass es von quadratischer Komplexität ist O (n ^ 2)

Wir können einen StringBuilder verwenden, der O(1) Komplexität für jeden Anhang hat. Nachfolgend finden Sie das rekursive Programm, das StringBuilder verwendet. Dies verwendet nur n/2 Stack-Frames, sodass der Platzbedarf geringer ist als der normale rekursive Aufruf, der wie s.charAt(s.length-1) + reverse(s.subString(0, s.length-2); aussehen würde. 

public class StringReverseRecursive {
    public static void main(String[] args) {
        String s = "lasrever gnirts fo noitatnemelpmi evisrucer a si sihT";
        StringBuilder sb = new StringBuilder(s);
        reverse(s, sb, 0, sb.length() - 1);
        System.out.println(sb.toString());
    }

    public static void reverse(String s, StringBuilder sb, int low, int high) {
        if (low > high)
            return;
        sb.setCharAt(low, s.charAt(high));
        sb.setCharAt(high, s.charAt(low));
        reverse(s, sb, ++low, --high);
    }
}
1
Princy Joy

Es hängt davon ab, was Sie als "besser" definieren. :-) Aber im Ernst; Ihre Lösung verwendet im Wesentlichen die maximale Rekursionstiefe. Wenn die Stapelgröße für Ihre Definition von "besser" von Belang ist, sollten Sie so etwas wie folgt verwenden:

public String reverseString(String s) {
   if (s.length() == 1) return s;
   return reverseString(s.substring(s.length() / 2, s.length() -1) + reverseString(0, s.length() / 2);
}
1
Paul Sonier

Dies ist, was ich gefunden habe, um zu arbeiten und rekursiv zu verwenden. Sie können str.length() als strLength-Argument übergeben

private static String reverse(String str, int strLength) {
    String result = "";
    if(strLength > 0)
        result = str.charAt(strLength - 1) + reverse(str, strLength - 1);
    return result;
}
1
Randy Turner

funktionsaufruf:

    //str:string to be reversed,i=0,j=str.length-1


    public void reverseString(String str,int i,int j)
    {

     if(i==j)
        {
         System.out.println(str);
         return;
        }

     char x=str.charAt(i);
     str=str.replace(str.charAt(i),str.charAt(j));
     str=str.replace(str.charAt(j),x);
     i++;j--;
     reverseString(str,i,j);
    }

diese Methode funktioniert auch ..

0
amit_183
String rev="";

public String reverseString(String s){
        if (s.length()==0) return "";
        return rev+s.substring(s.length()-1,s.length())+reverseString(s.substring(0, s.length()-1));
    }
0
Souji

Wenn Sie denken, dass weniger Code gut ist, dann .... 

static String reverse(String str){
    return str.length()>=2 ? str.charAt(str.length()-1) + reverse(str.substring(0,str.length()-1)) : str ;
}
0
Deepeshkumar

Es gibt bereits etwa 20 Antworten, aber ich werde auch meinen rekursiven Algorithmus einwerfen. Es kann ein wenig ausführlich sein, aber es ist zumindest lesbar. 

public static String reverseString(String str) {
   return reverseString("", str);
}

private static String reverseString(String result, String original) {
   if (original.length() == 0) {
      return result;
   } else {
      int length = original.length();
      String lastLetter = original.substring(length - 1, length);
      original = original.substring(0, length - 1);
      return reverseString(result + lastLetter, original);
   }
}

Der Code nimmt im Grunde rekursiv das Ende der Zeichenfolge an und verschiebt sie in den Vordergrund. Wenn der String, den wir umkehren möchten, beispielsweise "jam" ist, lautet das Ergebnis und die ursprünglichen Strings bei jedem Aufruf der Hilfsmethode wie folgt:

// result:  original:
// ""       jam
// m        ja
// ma       j
// maj      ""
0
anita
public static String rev(String name){
    if(name.length()>=1){
    System.out.print(name.charAt(name.length()-1)); 
    return rev(name.substring(0,name.length()-1));
    }
    else{
        return ""+name.substring(0);
    }
}
0
Sudhanshu

Sie können es mit einer externen Variablen versuchen und alle Zeichen nacheinander hinzufügen:

    public static String back="";

public static String reverseString(String str){


    if(str.length()==0){

        return back;

    }else {

        back+=str.charAt(str.length()-1);

        lees(str.substring(0,str.length()-1));


        return back;

    }

}

0
JBoy

Versuche Folgendes: 

public class reverse2
{
    public static void main(String name)
    {
    String revname=new StringBuffer(name).reverse().toString();
    System.out.println("original string " + name + " and the reverse of it is " + revname);
    }
}
0
user3223269

Reverse String unter Verwendung des rekursiven Methodenaufrufs.

Beispielcode

public static String reverseString(String s) {
    if (s.length() == 0) {
        return s;
    }
    else {
        return s.charAt(s.length() - 1) + reverseString(s.substring(0, s.length() - 1));
    }
}
0
Samowl

In diesem Zusammenhang ist dies völlig unnötig, aber Sie können Rekursion simulieren und Probleme mit Rekursionstiefe vermeiden, wenn Sie Ihren eigenen Stapel erstellen.

Sie können die Rekursion iterativ implementieren. Dies kann erforderlich sein, wenn Sie über Algorithmen verfügen, die von Natur aus rekursiv sind, aber auch für große Problemgrößen ausgeführt werden müssen.

String recIterReverse (String Word){

    Stack <String> stack = new Stack <String> ();
    stack.Push(Word);
    String result = "";

    while (!stack.isEmpty()){
        String temp = stack.pop();
        result = temp.charAt(0) + result;

        if (temp.length() > 1){
        stack.Push(temp.substring(1));
        }
    }

    return result;
}
0
user929404

Dies ist meine Lösung, ich habe in vielen Lösungen oben gesehen, dass wir die Saitenlänge erhalten, aber im Idealfall brauchen wir diese nicht. Das Zen soll Rekursion verwenden, einfach das erste Zeichen von String hacken und den Rest an die rekursive Methode übergeben. Yay!! wir haben die lösung. 

private static void printReverse(String str) {
            if (!str.isEmpty()) {
                String firstChar = str.substring(0, 1); //Get first char of String
                String newstr = str.substring(0, 0) + str.substring(1); // Get remaining string
                printReverse(newstr); // Recursion magic
                System.out.print(firstChar); //Output
            }
        }
0
vinni

Das ist definitiv, wie ich rekursiv einen String umkehren würde (obwohl es vielleicht schön wäre, ihn auf den Fall eines leeren Strings in Ihrem Zustand zu erweitern.) Ich glaube nicht, dass es einen grundsätzlich besseren Weg gibt.

BEARBEITEN: Es kann effizienter sein, ein Zeichenarray zu bearbeiten und eine "Cutoff" -Länge entlang der Rekursionskette zu durchlaufen, wenn Sie meine Drift erhalten, anstatt Teilstrings zu erstellen. Dies ist jedoch nicht wirklich eine Überlegung wert, da es überhaupt keine wirklich effiziente Technik ist.

0
mquander

Hier ist meine unveränderliche Version:

 String reverse(String str) {
    if(str.length()<2) return str;
    return  reverse(str.substring(1)) +str.charAt(0);
}

und rekursive Version des Schwanzes:

 String reverseTail(String str) {
    if(str.length()<2) return str;
    return str.charAt(str.length()-1)+ reverseTail(str.substring(0,str.length()-1));
0
scaevola

Wie Mehrdad bemerkt, ist es am besten, keine Rekursion zu verwenden. Wenn Sie es jedoch verwenden, können Sie sowohl den ersten als auch den letzten Buchstaben jedes Anrufs behalten, wodurch die Anzahl der rekursiven Anrufe halbiert wird. Das ist,

public String reverseString(String s){
    int len = s.length();

    if (len <= 1) {
        return s;
    }

    char fst = s.charAt(0);
    char lst = s.charAt(len - 1);

    return lst + reverseString(s.substring(1, len - 2)) + fst;
}

Dies behandelt auch den Fall der leeren Zeichenfolge. Ein StringBuilder mit entsprechender Kapazität zu übergeben, könnte die Sache vielleicht noch beschleunigen, aber das bleibt dem Leser als Übung überlassen;)

0
Stephan202
public class StringUtility {

public static void main(String[] args) {
    StringUtility stringUtility = new StringUtility();

    String input = "santosh123";
    int middle = input.length() / 2;
    middle = middle - 1;
    System.out.println(stringUtility.stringReverse(input, middle));
}

public String stringReverse(String input, int middle) {

    if (middle == -1) {

        System.out.println("if");
        return input;

    } else {

        System.out.println("else");
        input = swapChar(input, middle);
        middle = middle - 1;
        return stringReverse(input, middle);

    }

}

private String swapChar(String input, int middle) {
    StringBuilder str = new StringBuilder(input);
    char begin = str.charAt(middle);
    int endIndex = input.length() - middle - 1;
    char end = str.charAt(endIndex);
    str.setCharAt(middle, end);
    str.setCharAt(endIndex, begin);
    System.out.println(str + "  " + middle + "  " + endIndex);
    return str.toString();
}

}
0
Santosh
public String reverseString (String s) {

    if (s != null && s.length () > 0 ) {
        rev = rev + s.substring (s.length () - 1);
        reverseString (s.substring (0, s.length () - 1));
    }
    return rev;

}
0

Sie erfassen die Grundidee, aber das Extrahieren des letzten Zeichens verbessert die Übersichtlichkeit nicht. Ich würde Folgendes vorziehen, andere nicht:

public class Foo
{
    public static void main(String[] argv) throws Exception
    {
        System.out.println(reverse("a"));
        System.out.println(reverse("ab"));
        System.out.println(reverse("abc"));
    }


    public final static String reverse(String s)
    {
        // oft-repeated call, so reduce clutter with var
        int length = s.length();

        if (length <= 1)
            return s;
        else
            return s.substring(length - 1) + reverse(s.substring(0, length - 1));
    }
}
0
kdgregory