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

Question

Ich habe heute mit Rekursion rumgespielt. Oft eine Programmiertechnik, die nicht genug benutzt wird.

Ich legte fest, um eine Zeichenfolge rekursiv umzukehren. Hier ist, was ich gefunden habe:

//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?

Answer 1

Der beste Weg ist Rekursion nicht zu verwenden. Diese Dinge werden normalerweise verwendet, um den Schülern das Rekursionskonzept beizubringen, nicht die eigentlichen Best Practices. So wie du es machst, ist es in Ordnung. Verwenden Sie keine Rekursion in Java für diese Art von Sachen in realen Apps;)

PS. Abgesehen was gerade gesagt ich, werde ich "" als Basisfall meiner rekursive Funktion wählen:

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

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

Answer 2

, die definitiv ist, wie ich über gehen würde, rekursiv ein String Umkehren (obwohl es schön, könnte es zu dem verlängern Fall einer leeren Schnur in deinem Zustand.) Ich glaube nicht, dass es einen grundsätzlich besseren Weg gibt.

EDIT: Es kann effizienter sein, auf einem Character-Array zu arbeiten und eine "cutoff" -Länge entlang der Rekursionskette zu durchlaufen, wenn Sie meine Drift bekommen, anstatt Teilstrings zu machen. Das ist jedoch nicht wirklich lohnend, da es überhaupt keine besonders effiziente Technik ist.

Answer 3

Als Mehrdad notiert, ist es am besten, keine Rekursion zu verwenden. Wenn Sie es jedoch verwenden, können Sie sowohl das erste als auch das letzte Zeichen für jeden Aufruf beibehalten, wodurch die Anzahl der rekursiven Aufrufe halbiert wird. Das heißt,

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. Vielleicht vorbei mit der entsprechenden Kapazität entlang einem String Dinge beschleunigen würde noch mehr, aber das den Leser als Übung übrig;)

Answer 4

Sie die Grundidee erfassen, aber das letzte Zeichen zu extrahieren Klarheit nicht verbessert. Ich würde Folgendes bevorzugen, 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)); 
    } 
} 

Answer 5

Sie wollen nicht zu tief nisten. Teilen und Herrschen ist der Weg zu gehen. Reduziert außerdem die Gesamtgröße temporärer Strings und ist für eine 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 geprüft - das ist Stackoverflow.)

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

Bearbeiten: Nur zum Spaß, eine Tail-Rekursion-freundliche 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 Behandlung von Ersatzpaaren ist dem interessierten Leser überlassen.

Answer 6

Nur zum Teufel, hier ist eine Tail-rekursive Methode mit StringBuilder (die im Allgemeinen über die Manipulation String s empfohlen wird).

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 in vielen Jahren nicht mit Java beschäftigt, aber das sollte ungefähr richtig sein.

Answer 7

Es hängt davon ab, was Sie als "besser" definieren. :-) Aber im Ernst; Ihre Lösung verwendet im Wesentlichen die maximale Rekursionstiefe; wenn Stapelgröße von der Sorge um Ihre Definition von „besser“ ist, dann würden Sie besser dran, so etwas wie dies mit:

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

Answer 8

Wenn Sie vorhaben, dies zu tun, wollen Sie sich auf einen Charakter bedienen Array, weil ein String unveränderlich ist und du überall Strings kopieren wirst, wenn du es so machst.

Dies ist nicht getestet und völlig Bewusstseinsstrom. Wahrscheinlich hat es 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); 
    } 

Answer 9

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

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

Answer 10

Sie können mit einer externen Variablen versuchen, und fügen Sie 1 von 1 alle Zeichen:

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; 

    } 

}

Answer 11

Here ist meine unveränderliche Version:

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

und Tail rekursive Version:

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

Answer 12

hier ist meine rekursive Reverse-Funktion, die feinen

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

Answer 13

In diesem Zusammenhang arbeitet, dies völlig unnötig ist, aber Sie können Rekursion simulieren und Rekursionstiefe Probleme vermeiden, wenn Sie Ihre eigene Stack zu machen.

Sie können Rekursion iterativ implementieren, was erforderlich sein kann, wenn Sie Algorithmen haben, die inhärent rekursiv sind, aber sie auch für große Problemgrößen ausführen 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; 
} 

Answer 14

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 auch funktioniert ..

Answer 15

Versuchen Sie 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); 
    } 
} 

Answer 16

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

Answer 17

Das ist, was ich Arbeit gefunden habe und verwende rekursiv.Sie können str.length() als strlength Argument

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

Answer 18

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

Answer 19

public static String reverse(String s){ 

    int n = s.length()-1; 

    if(n >=0) 
    return s.substring(s.length()-1)+ReverseString(s.substring(0,n--)); 
    else return ""; 
} 

Answer 20

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; 

} 

Answer 21

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

} 

Answer 22

passieren Wenn Sie weniger Code denken dann gut ist ....

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

Answer 23

Es gibt etwa 20 Antworten schon, aber ich werde auch meinen rekursiven Algorithmus einwerfen. Es kann ein wenig wortreich 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 rekursiv das Ende der Zeichenfolge und verschiebt es vor. Zum Beispiel, wenn die Zeichenfolge wir umkehren wollen, ist „jam“, dann wird jedes Mal, wenn die Helfer-Methode aufgerufen wird, Ergebnis und Original-Zeichenkette sind wie folgt:

// result: original: 
// ""  jam 
// m  ja 
// ma  j 
// maj  "" 

Answer 24

Reverse-String des rekursive Methodenaufruf.

Sample Code

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

Answer 25

Dies ist meine Lösung, sah ich in vielen Lösungen, die oben wir die Stringlänge bekommen, aber idealerweise brauchen wir nicht. Das Zen ist Rekursion, hacken Sie einfach das erste Zeichen der Zeichenfolge und übergeben Sie den Rest an die rekursive Methode. 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 
      } 
     }