Reverse a String

Q: Wie hoch ist die Zeitkomplexität beim Umkehren eines Strings?

Das Umkehren benötigt O(n) Zeit, da jedes Zeichen an eine neue Position verschoben werden muss und jedes genau einmal verarbeitet wird. Das Erstellen einer neuen Zeichenfolge benötigt zusätzlich O(n) Speicherplatz. Das Vertauschen mit zwei Zeigern benötigt nur O(1) zusätzlichen Speicherplatz, wenn sich die Zeichen bereits in einem veränderbaren Array befinden.

Q: Wie kehrst du eine Zeichenkette ohne eine eingebaute Umkehrfunktion um?

Kopiere die Zeichen in ein Array, platziere an jedem Ende einen Zeiger, vertausche die beiden Zeichen und bewege die Zeiger aufeinander zu, bis sie sich treffen. Alternativ kannst du in einer Schleife vom letzten Index bis zum ersten zurückgehen und jedes Zeichen an einen Builder anhängen. Beides erzeugt den umgekehrten String in einem Durchlauf.

Q: Kannst du einen String direkt umkehren?

Nur wenn die Zeichen in einem veränderbaren Puffer gespeichert sind, etwa in einem char -Array in C, Java oder C#, einer Liste in Python oder einem std::string in C++. Zeichenfolgen in Java, Python, JavaScript und vielen anderen Sprachen sind unveränderlich. Daher kopierst du sie in ein Array, vertauschst die Zeichen darin und erstellst eine neue Zeichenfolge. Der Vertauschungsschritt selbst erfolgt in beiden Fällen direkt an Ort und Stelle.

Q: Warum endet die Schleife mit zwei Zeigern in der Mitte?

Jeder Tausch bringt zwei Zeichen an ihre endgültigen Positionen, sodass nach n / 2 Tauschen jedes Zeichen dort ist, wo es hingehört. Über die Mitte hinaus weiterzumachen, tauscht dieselben Paare wieder zurück und macht die Arbeit rückgängig. Ist die Länge ungerade, befindet sich das mittlere Zeichen bereits an seinem eigenen Spiegelindex und muss nicht getauscht werden.

EinsteigerArrays und Strings Zwei Zeiger

+10

Du erhältst eine Zeichenfolge s, die aus englischen Buchstaben und Ziffern besteht. Gib eine neue Zeichenfolge mit denselben Zeichen in umgekehrter Reihenfolge zurück, sodass das letzte Zeichen zuerst und das erste zuletzt kommt. Behalte jedes Zeichen genau so bei, wie es ist, einschließlich seiner Groß- und Kleinschreibung.

Funktion

reverseString(s: string) → string

sstring: die umzukehrende Zeichenkette
Gibt zurückstring: die Zeichen von s in umgekehrter Reihenfolge

Einschränkungen

1 ≤ s.length ≤ 10⁴
s enthält nur englische Buchstaben (a bis z, A bis Z) und Ziffern (0 bis 9).

Beispiele

Eingabe: s = "Coddy2026"
Ausgabe: "6202yddoC"
Erklärung: Lies Coddy2026 vom letzten Zeichen bis zum ersten: 6, 2, 0, 2, dann y, d, d, o und schließlich das große C.

Eingabe: s = "noon"
Ausgabe: "noon"
Erklärung: noon ist ein Palindrom, daher ist die Umkehrung dasselbe Wort. Die äußeren n tauschen die Plätze, dann tun es die beiden o.

+14 versteckte Tests beim Einreichen

Weiterführende Frage

Wie würdest du die Reihenfolge der Wörter in einem Satz umkehren, sodass aus hello big world world big hello wird, während die Buchstaben jedes Wortes in ihrer Reihenfolge bleiben?

Tipps

Öffne sie nacheinander. Jeder verrät ein bisschen mehr.

0 von 3 geöffnet

Lösung

Jedes Zeichen hat ein festes Ziel: Das Zeichen am Index i gehört an den Index n-1-i. Du kannst die Zeichen in dieser Reihenfolge in einen neuen String schreiben oder sie paarweise von beiden Enden aus vertauschen. Die Variante mit dem Vertauschen wird in Vorstellungsgesprächen häufig verlangt, weil dieselbe Zwei-Zeiger-Bewegung ein Array direkt umkehrt und ein Palindrom überprüft.

Kopiere die Zeichen von hinten

Idee

Die Umkehrung von s beginnt mit dem letzten Zeichen von s, geht mit dem vorletzten weiter und endet mit dem ersten. Gehe also mit einem Index von n-1 abwärts bis 0 und hänge jedes Zeichen, sobald du es erreichst, an die Antwort an. Für Coddy2026 hängst du 6, 2, 0, 2, y und so weiter an, was 6202yddoC ergibt.

Jedes Zeichen wird einmal gelesen und einmal geschrieben, daher beträgt der Aufwand O(n). Die Antwort ist eine zweite Zeichenkette mit n Zeichen, was O(n) zusätzlichen Speicherplatz benötigt.

Wie du die Zeichen anhängst, ist entscheidend. Wenn du mit + ein Zeichen an eine unveränderliche Zeichenkette anhängst, wird jedes Mal die gesamte Zeichenkette kopiert. Bei n = 10^4 sind das etwa 5 × 10^7 Zeichenkopien. Sammle die Zeichen in einer Liste oder einem String-Builder und füge sie am Ende einmal zusammen.

Algorithmus

Erstelle eine leere Liste oder einen StringBuilder für die Antwort.
Durchlaufe i von n-1 abwärts bis 0.
Füge s[i] zur Antwort hinzu.
Füge die Antwort zu einem String zusammen und gib ihn zurück.

def reverseString(s):
    result = []
    for i in range(len(s) - 1, -1, -1):
        result.append(s[i])
    return "".join(result)

Von beiden Enden aus mit zwei Zeigern tauschen

Idee

Beim Umkehren werden die Zeichen von außen nach innen paarweise vertauscht. Das erste und das letzte tauschen die Plätze, dann das zweite und das vorletzte und so weiter in Richtung Mitte. Setze einen Zeiger left auf Index 0 und einen Zeiger right auf Index n-1, vertausche die beiden Zeichen und bewege beide Zeiger jeweils einen Schritt nach innen.

Höre auf, wenn sich die Zeiger treffen oder kreuzen. Bei noon starten die Zeiger bei 0 und 3, bewegen sich dann zu 1 und 2 und kreuzen sich anschließend nach zwei Vertauschungen. Bei einer ungeraden Länge wie xYz treffen sie sich beim mittleren Zeichen, das bereits an seinem endgültigen Platz steht und daher nie berührt wird. Jede Vertauschung bringt zwei Zeichen an ihre endgültigen Plätze, daher reichen n / 2 Vertauschungen aus.

Für die Vertauschungen selbst wird nur eine temporäre Variable benötigt, also zusätzlicher Speicherplatz von O(1). In den meisten Sprachen lässt sich eine Zeichenfolge nicht direkt ändern. Deshalb kopierst du sie zunächst in ein Zeichenarray, was O(n) kostet. In einem Vorstellungsgespräch, in dem die Eingabe bereits ein Zeichenarray ist, kehrt dieser Ansatz die Reihenfolge ganz ohne zusätzlichen Speicher um.

Algorithmus

Kopiere s in ein Zeichenarray.
Setze left = 0 und right = n-1.
Solange left < right gilt, vertausche die Zeichen an den Positionen left und right, addiere dann 1 zu left und subtrahiere 1 von right.
Wandle das Array zurück in eine Zeichenkette um und gib sie zurück.

def reverseString(s):
    chars = list(s)
    left, right = 0, len(chars) - 1
    while left < right:
        chars[left], chars[right] = chars[right], chars[left]
        left += 1
        right -= 1
    return "".join(chars)

Stolperfallen und Grenzfälle

Das Umkehren sieht nach einer einzigen Zeile aus, doch die Fehler verstecken sich in den Schleifengrenzen und darin, wie das Ergebnis aufgebaut wird.

left bis n-1 durchlaufen. Jenseits der Mitte wird jedes Paar ein zweites Mal vertauscht, sodass die Zeichenfolge unverändert zurückkommt. Stoppe bei left < right.
Die Rückwärtsschleife bei n statt bei n-1 beginnen, wodurch eine Position hinter dem Ende gelesen wird. In Lua und R laufen die Indizes stattdessen von 1 bis n.
Das Ergebnis mit result = result + ch in einer unveränderlichen Zeichenfolge aufbauen. Bei jedem Schritt wird alles bisher Erstellte kopiert, wodurch eine lineare Aufgabe bei langen Eingaben quadratisch wird.
Das abschließende '\0' in C vergessen. Ein Puffer mit n Bytes ist um eins zu kurz; reserviere n + 1.
Ohne temporäre Variable vertauschen: Nach chars[left] = chars[right] ist das alte linke Zeichen weg, es sei denn, deine Sprache vertauscht beide Werte auf einmal.

Häufige Fragen4

Wie hoch ist die Zeitkomplexität beim Umkehren eines Strings?

Das Umkehren benötigt O(n) Zeit, da jedes Zeichen an eine neue Position verschoben werden muss und jedes genau einmal verarbeitet wird. Das Erstellen einer neuen Zeichenfolge benötigt zusätzlich O(n) Speicherplatz. Das Vertauschen mit zwei Zeigern benötigt nur O(1) zusätzlichen Speicherplatz, wenn sich die Zeichen bereits in einem veränderbaren Array befinden.

Wie kehrst du eine Zeichenkette ohne eine eingebaute Umkehrfunktion um?

Kopiere die Zeichen in ein Array, platziere an jedem Ende einen Zeiger, vertausche die beiden Zeichen und bewege die Zeiger aufeinander zu, bis sie sich treffen. Alternativ kannst du in einer Schleife vom letzten Index bis zum ersten zurückgehen und jedes Zeichen an einen Builder anhängen. Beides erzeugt den umgekehrten String in einem Durchlauf.

Kannst du einen String direkt umkehren?

Nur wenn die Zeichen in einem veränderbaren Puffer gespeichert sind, etwa in einem char-Array in C, Java oder C#, einer Liste in Python oder einem std::string in C++. Zeichenfolgen in Java, Python, JavaScript und vielen anderen Sprachen sind unveränderlich. Daher kopierst du sie in ein Array, vertauschst die Zeichen darin und erstellst eine neue Zeichenfolge. Der Vertauschungsschritt selbst erfolgt in beiden Fällen direkt an Ort und Stelle.

Warum endet die Schleife mit zwei Zeigern in der Mitte?

Jeder Tausch bringt zwei Zeichen an ihre endgültigen Positionen, sodass nach n / 2 Tauschen jedes Zeichen dort ist, wo es hingehört. Über die Mitte hinaus weiterzumachen, tauscht dieselben Paare wieder zurück und macht die Arbeit rückgängig. Ist die Länge ungerade, befindet sich das mittlere Zeichen bereits an seinem eigenen Spiegelindex und muss nicht getauscht werden.

Python

def reverseString(s):
    # Schreibe hier Code

Testfälle

Fall 1

Fall 2

Fall 3

Eingabe

s = "Coddy2026"

Erwartet

"6202yddoC"