webentwicklung-frage-antwort-db.com.de

Was ist der effizienteste Algorithmus zum Umkehren eines Strings in Java?

Was ist der effizienteste Weg, eine Zeichenfolge in Java umzukehren? Sollte ich eine Art xor-Operator verwenden? Der einfachste Weg wäre, alle Zeichen in einen Stapel zu setzen und sie wieder in eine Zeichenfolge zu setzen, aber ich bezweifle, dass dies ein sehr effizienter Weg ist. 

Und bitte sagen Sie mir nicht, dass ich einige eingebaute Funktionen in Java verwenden soll. Ich bin daran interessiert zu lernen, wie man eine effiziente Funktion nicht verwendet, aber nicht weiß, warum sie effizient ist oder wie sie aufgebaut ist. 

34
Hultner

Sie sagen, Sie möchten den effizientesten Weg kennen, und Sie möchten nicht wissen, wie Sie dies standardmäßig tun. Dann sage ich dir: RTSL (lese die Quelle, luke):

Überprüfen Sie den Quellcode für AbstractStringBuilder # reverse , der von StringBuilder # reverse aufgerufen wird. Ich wette, es tut etwas, was Sie für eine robuste Umkehroperation nicht in Betracht gezogen hätten.

49
Tom

Im Folgenden werden UTF-16-Ersatzpaare nicht behandelt.

public static String reverse(String orig)
{
    char[] s = orig.toCharArray();
    int n = s.length;
    int halfLength = n / 2;
    for (int i=0; i<halfLength; i++)
    {
        char temp = s[i];
        s[i] = s[n-1-i];
        s[n-1-i] = temp;
    }
    return new String(s);
}
35
Simon Nickerson

Sie sagten, dass Sie es nicht einfach machen wollen, aber für Googling sollten Sie StringBuilder.reverse verwenden:

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

Wenn Sie es selbst implementieren müssen, iterieren Sie die Zeichen in umgekehrter Reihenfolge und hängen Sie sie an einen StringBuilder an. Sie müssen vorsichtig sein, wenn es Ersatzpaare gibt (oder geben kann), da diese nicht rückgängig gemacht werden sollten. Die oben gezeigte Methode erledigt dies automatisch für Sie, weshalb Sie sie nach Möglichkeit verwenden sollten.

20
Mark Byers

In einem alten Beitrag und einer Frage wurden jedoch immer noch keine Antworten zur Rekursion gefunden. Die rekursive Methode invertiert die angegebene Zeichenkette s, ohne die eingebauten jdk-Funktionen weiterzuleiten

    public static String reverse(String s) {
    if (s.length() <= 1) {
        return s;
    }
    return reverse(s.substring(1)) + s.charAt(0);
}

`

8
cocoper

Der schnellste Weg wäre, die reverse()-Methode für die StringBuilder- oder StringBuffer-Klassen zu verwenden :)

Wenn Sie es selbst implementieren möchten, können Sie das Zeichen-Array abrufen, ein zweites Zeichen-Array zuweisen und die Zeichen verschieben.

String reverse(String str) {
    char[] c = str.getCharArray
    char[] r = new char[c.length];
    int    end = c.length - 1

    for (int n = 0; n <= end; n++) {
        r[n] = c[end - n];
    }

    return new String(r);
}

Sie könnten auch die Hälfte der Arraylänge ausführen und die Zeichen austauschen, die Überprüfungen verlangsamen die Sache wahrscheinlich.

5
rsp

Ich bin mir nicht wirklich sicher, was Sie meinen, wenn Sie sagen, Sie brauchen einen effizienten Algorithmus.

Die Möglichkeiten zum Umkehren eines Strings, den ich mir vorstellen kann, sind (sie werden alle bereits in anderen Antworten erwähnt):

  1. Verwenden Sie einen Stapel (Ihre Idee).

  2. Erstellen Sie einen neuen umgekehrten String, indem Sie nacheinander Zeichen in umgekehrter Reihenfolge vom ursprünglichen String zu einem leeren String/StringBuilder/char [] hinzufügen.

  3. Tauschen Sie alle Zeichen in der ersten Hälfte des Strings mit der entsprechenden Position in der letzten Hälfte aus (d. H. Das i-te Zeichen wird mit dem Zeichen (length-i-1) ausgetauscht).

Die Sache ist, dass alle dieselbe Laufzeitkomplexität : O (N) haben. Man kann also nicht wirklich behaupten, dass einer für sehr große Werte von N (d. H. Sehr große Strings) wesentlich besser ist als die anderen.

Für die dritte Methode gibt es eine Sache, für die anderen beiden ist O(N) zusätzlicher Speicherplatz erforderlich (für den Stapel oder den neuen String), während Swaps an Ort und Stelle ausgeführt werden können. Da Strings jedoch in Java unveränderlich sind, müssen Sie auf jeden Fall einen neu erstellten StringBuilder/char [] austauschen und benötigen daher O(N) zusätzlichen Speicherplatz.

3
MAK
public class ReverseInPlace {

  static char[]  str=null;

    public static void main(String s[]) {
      if(s.length==0)
        System.exit(-1);

       str=s[0].toCharArray();

       int begin=0;
       int end=str.length-1;

       System.out.print("Original string=");
       for(int i=0; i<str.length; i++){
         System.out.print(str[i]);
       }

       while(begin<end){
          str[begin]= (char) (str[begin]^str[end]);
          str[end]= (char)   (str[begin]^str[end]);
          str[begin]= (char) (str[end]^str[begin]);

          begin++;
          end--;       
       }

       System.out.print("\n" + "Reversed string=");
       for(int i=0; i<str.length; i++){
         System.out.print(str[i]);
       }

    }
}
3
abiolaaye
private static String reverse(String str) {
    int i = 0;
    int j = str.length()-1;
    char []c = str.toCharArray();
    while(i <= j){
        char t = str.charAt(i);
        c[i] = str.charAt(j);
        c[j]=t;
        i++;
        j--;
    }
    return new String(c);
}
2
Kuldeep Singh

Ich denke, wenn Sie wirklich kein Leistungsproblem haben, sollten Sie sich für die am besten lesbare Lösung entscheiden:

StringUtils.reverse("Hello World");
2
Marcin Szymczak
char* rev(char* str)
    {
    int end= strlen(str)-1;
    int start = 0;

    while( start<end )
    {
    str[start] ^= str[end];
    str[end] ^= str[start];
    str[start]^= str[end];

    ++start;
    --end;
    }

    return str;
}

===========================

Frage mich, wie es funktioniert?

Erste Operation: 

x1 = x1 XOR x2

x1: 1   0   0
x2: 1   1   1
New x1: 0   1   1

Zweite Operation 

x2 = x2 XOR x1

x1: 0   1   1
x2: 1   1   1
New x2: 1   0   0
//Notice that X2 has become X1 now

Dritte Operation: 

x1 = x1 XOR x2
x1: 0   1   1
x2: 1   0   0
New x1: 1   1   1
//Notice that X1 became X2
1
Bhojal Gelda

Ich würde es einfach so machen, ohne eine einzige Funktionsfunktion zu verwenden. Nur die String-Klasse ist ausreichend.

public class MyStringUtil {

    public static void main(String[] args) {
        String reversedString = reverse("StringToReverse");
        System.out.println("Reversed String : " + reversedString);
    }

    /**
     * Reverses the given string and returns reversed string
     * 
     * @param s Input String
     * @returns reversed string
     */
    private static String reverse(String s) {
        char[] charArray = s.toCharArray(); // Returns the String's internal character array copy
        int j = charArray.length - 1;
        for (int i = 0; charArray.length > 0 && i < j; i++, j--) {
            char ch = charArray[i];
            charArray[i] = charArray[j];
            charArray[j] = ch;
        }
        return charArray.toString();
    }
}

Prüfen Sie. Prost!!

1
Vivek

Wenn Sie keine eingebaute Funktion verwenden möchten, müssen Sie mit der Zeichenfolge zu den Komponententeilen zurückkehren: einem Array von Zeichen.

Nun stellt sich die Frage, wie man ein Array am besten umkehren kann. Die Antwort auf diese Frage hängt in der Praxis auch von der Speichernutzung ab (für sehr große Zeichenfolgen), in der Theorie wird die Effizienz in diesen Fällen jedoch bei Array-Zugriffen gemessen. 

Am einfachsten ist es, ein neues Array zu erstellen und es mit den Werten zu füllen, die Sie beim Umkehren des ursprünglichen Arrays durchlaufen und das neue Array zurückgeben. (Obwohl mit einer temporären Variablen dies auch möglich ist, können Sie dies auch ohne zusätzliches Array tun, wie in der Antwort von Simon Nickerson).

Auf diese Weise greifen Sie für ein Array mit n Elementen genau einmal auf jedes Element zu. Dadurch ergibt sich eine Effizienz von O (n). 

1
NomeN

String verwenden: 

String abc = "abcd";
int a= abc.length();

String reverse="";

for (int i=a-1;i>=0 ;i--)
{
    reverse= reverse + abc.charAt(i);
}
System.out.println("Reverse of String abcd using invert array is :"+reverse);

StringBuilder verwenden:

    String abc = "abcd";
    int a= abc.length();
    StringBuilder sb1 = new StringBuilder();

    for (int i=a-1;i>=0 ;i--)
    {
        sb1= sb1.append(abc.charAt(i));
    }
    System.out.println("Reverse of String abcd using StringBuilder is :"+sb1);
0
jags
public static string getReverse(string str)
{
    char[] ch = str.ToCharArray();
    string reverse = "";
    for (int i = str.Length - 1; i > -1; i--)
    {
        reverse += ch[i];
    }
    return reverse;
}

//using in-built method reverse of Array
public static string getReverseUsingBulidingFunction(string str)
{
    char[] s = str.ToCharArray();
    Array.Reverse(s);
    return new string(s);
}


public static void Main(string[] args)
{
    string str = "123";
    Console.WriteLine("The reverse string of '{0}' is: {1}",str,getReverse(str));
    Console.WriteLine("The reverse string of '{0}' is: {1}", str, getReverseUsingBulidingFunction(str));
    Console.ReadLine();
}
0
Dipitak

Eine Variante kann das Austauschen der Elemente sein. 

int n = length - 1;
char []strArray = str.toCharArray();
for (int j = 0; j < n; j++) {
   char temp = strArray[j];
   char temp2 = strArray[n];
   strArray[j] = temp2;
   strArray[n] = temp;
   n--;
  }
0
Naren
public static void main(String[] args){
    String string ="abcdefghijklmnopqrstuvwxyz";
    StringBuilder sb = new StringBuilder(string);
    sb.reverse();

    System.out.println(sb);
}
0
Dan

Mehrere Threads verwenden, um die Elemente auszutauschen:

    final char[] strArray = str.toCharArray();

    IntStream.range(0, str.length() / 2).parallel().forEach(e -> {
        final char tmp = strArray[e];
        strArray[e] = strArray[str.length() - e - 1];
        strArray[str.length() - e - 1] = tmp;
    });
    return new String(strArray);
0
user3666072

Natürlich ist dies der effizienteste Weg:

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

Wenn Sie das aber nicht mögen, empfehle ich stattdessen Folgendes:

public String reverseString(String str)
{
    String output = "";
    int len = str.length();
    for(int k = 1; k <= str.length(); k++, len--)
    {
        output += str.substring(len-1,len);
    }
    return output;
}
0
GlennTheAlien
static String ReverseString(String input) {
    var len = input.Length - 1;
    int i = 0;
    char[] revString = new char[len+1];
    while (len >= 0) {
        revString[i] = input[len];
        len--; 
        i++;
    }
    return new string(revString);   
}

warum können wir uns nicht an die einfachste Schleife halten und die Zeichen lesen und immer wieder zum Zeichen-Array hinzufügen? Ich bin auf ein Whiteboard-Interview gestoßen, in dem der Interviewer Einschränkungen festgelegt hat, StringBuilder und eingebaute Funktionen nicht zu verwenden.

0
jidh
public static String Reverse(String Word){
        String temp = "";
        char[] arr = Word.toCharArray();
        for(int i = arr.length-1;i>=0;i--){
            temp = temp+arr[i];
        }
        return temp;
    }
0
saad