Reverse Words in a String

Q: Wie hoch ist die Zeitkomplexität von „Reverse Words in a String“?

Beide Ansätze benötigen für einen String der Länge n eine Laufzeit von O(n) , da jedes Zeichen eine konstante Anzahl von Malen gelesen und geschrieben wird. Das Aufteilen benötigt O(n) zusätzlichen Speicherplatz für die Wortliste. Das Umkehren des gesamten Strings und anschließend jedes einzelnen Wortes benötigt O(1) zusätzlichen Speicherplatz in einem Zeichenarray, das du bearbeiten kannst.

MittelArrays und Strings Zwei Zeiger

+10

Du erhältst eine Zeichenfolge s, die aus Wörtern und Leerzeichen besteht. Ein Wort ist eine Folge aus Buchstaben und Ziffern ohne Leerzeichen darin. Wörter können durch mehr als ein Leerzeichen getrennt sein, und s kann mit Leerzeichen beginnen oder enden.

Gib die Wörter in umgekehrter Reihenfolge zurück, verbunden durch genau ein Leerzeichen und ohne Leerzeichen am Anfang oder Ende. Jedes Wort behält seine Schreibweise bei; nur die Reihenfolge der Wörter ändert sich.

Funktion

reverseWords(s: string) → string

sstring: Buchstaben, Ziffern und Leerzeichen, die mindestens ein Wort enthalten
Gibt zurückstring: die Wörter von s in umgekehrter Reihenfolge, durch einzelne Leerzeichen getrennt

Einschränkungen

1 ≤ s.length ≤ 10⁴
s enthält nur englische Buchstaben, Ziffern und Leerzeichen.
s enthält mindestens ein Wort.

Beispiele

Eingabe: s = "Coddy runs in 15 languages"
Ausgabe: "languages 15 in runs Coddy"
Erklärung: Die Wörter sind Coddy, runs, in, 15 und languages. Von hinten nach vorn gelesen ergeben sie languages 15 in runs Coddy; 15 zählt als Wort, weil Wörter Ziffern enthalten können.

Eingabe: s = " practice makes progress "
Ausgabe: "progress makes practice"
Erklärung: Die Leerzeichen an beiden Enden werden entfernt, und Folgen aus zwei und drei Leerzeichen zwischen den Wörtern schrumpfen auf eines. Die drei Wörter erscheinen in umgekehrter Reihenfolge: progress makes practice.

Eingabe: s = " single "
Ausgabe: "single"
Erklärung: Eine Liste aus einem Wort liest sich rückwärts genauso. Nur die Leerzeichen darum herum entfallen, daher lautet die Antwort single.

Weiterführende Frage

Kannst du die Wörter umkehren, aber die Abstände von s beibehalten: dieselben Leerzeichenfolgen mit denselben Längen in derselben Reihenfolge?

Lösung

Die Wortreihenfolge wird einmal umgedreht; an den Leerzeichen scheitern die Lösungen. Leerzeichen am Anfang oder Ende sowie wiederholte Leerzeichen zwischen Wörtern müssen verschwinden, sodass die Antwort genau ein Leerzeichen zwischen den Wörtern enthält. Du kannst den Text in eine Wortliste aufteilen oder die ganze Zeichenfolge und anschließend jedes Wort innerhalb eines Arrays umdrehen.

In Wörter aufteilen und in umgekehrter Reihenfolge zusammenfügen

Idee

Teile s in seine Wörter auf, kehre die Liste um und verbinde sie mit einzelnen Leerzeichen. Beim Aufteilen ist Sorgfalt nötig: Wenn du " practice makes progress " an jedem einzelnen Leerzeichen aufteilst, entstehen um die drei Wörter herum sechs leere Teile. Entferne die leeren Teile, und die Liste lautet practice, makes, progress.

Beim Aufteilen wird jedes Zeichen einmal gelesen und beim Verbinden jedes beibehaltene Zeichen einmal geschrieben. Daher beträgt die Laufzeit für eine Zeichenfolge der Länge n O(n). Die Wortliste und das Ergebnis benötigen zusätzlich O(n) Speicherplatz.

Algorithmus

Teile s an den Leerzeichen auf.
Entferne die leeren Teile.
Kehre die Wortliste um.
Füge die Wörter mit jeweils einem Leerzeichen dazwischen zusammen und gib das Ergebnis zurück.

def reverseWords(s):
    # split() with no argument treats any run of spaces as one separator
    # and ignores spaces at both ends.
    words = s.split()
    words.reverse()
    return " ".join(words)

Die gesamte Zeichenkette umkehren, dann jedes Wort

Idee

Wenn du die gesamte Zeichenkette umdrehst, stehen die Wörter zwar in der richtigen Reihenfolge, aber jedes einzelne ist rückwärts geschrieben: Coddy runs in 15 languages wird zu segaugnal 51 ni snur yddoC. Wenn du anschließend jedes Wort einzeln umdrehst, erhältst du languages 15 in runs Coddy.

Die Leerzeichen werden im selben Durchlauf behandelt. Ein read-Index durchläuft das umgekehrte Array und überspringt Leerzeichen; ein write-Index markiert, wohin das nächste beizubehaltende Zeichen kommt. Beim Kopieren wird kein Zeichen überschrieben, das du noch brauchst, denn write überschreitet read nie: Das Leerzeichen, das vor einem Wort geschrieben wird, steht für mindestens ein Leerzeichen, das read übersprungen hat.

Jedes Zeichen wird höchstens einmal kopiert und höchstens zweimal vertauscht, daher beträgt die Laufzeit O(n), mit O(1) zusätzlichem Speicherplatz bei einem Zeichenpuffer, den du bearbeiten kannst. Zeichenketten werden hier als Werte übergeben, daher erstellt jede Lösung eine Arbeitskopie von s: insgesamt O(n) Speicher.

Algorithmus

Kopiere s in ein Zeichenarray und kehre das gesamte Array um.
Durchlaufe das Array mit einem Leseindex und überspringe Leerzeichen.
Schreibe bei jedem Wort zuerst ein Leerzeichen, außer beim ersten Wort, und kopiere dann die Zeichen des Wortes an den Schreibindex.
Kehre den kopierten Abschnitt um, damit das Wort vorwärts gelesen wird.
Gib die ersten write Zeichen zurück.

def reverseWords(s):
    chars = list(s)

    def reverse(lo, hi):
        while lo < hi:
            chars[lo], chars[hi] = chars[hi], chars[lo]
            lo += 1
            hi -= 1

    n = len(chars)
    reverse(0, n - 1)  # words in the right order, each spelled backwards
    write = 0
    read = 0
    while read < n:
        if chars[read] == " ":
            read += 1
            continue
        if write > 0:
            chars[write] = " "  # one space before every word but the first
            write += 1
        start = write
        while read < n and chars[read] != " ":
            chars[write] = chars[read]
            write += 1
            read += 1
        reverse(start, write - 1)  # spell the word forwards again
    return "".join(chars[:write])

Stolperfallen und Grenzfälle

An einem einzelnen Leerzeichen aufteilen und jedes Teilstück beibehalten. "a b" wird in a, ein leeres Teilstück und b aufgeteilt, und beim Zusammenfügen kommen die zwei Leerzeichen zurück: "b a".
Darauf vertrauen, dass beim Aufteilen die Enden entfernt werden. Javas split(" ") entfernt leere Teilstücke am Ende, behält sie aber am Anfang bei, sodass bei " a b" weiterhin eines übrig bleibt.
Nach jedem Wort ein Leerzeichen hinzufügen, auch nach dem letzten, sodass die Antwort mit einem Leerzeichen endet. Setze das Leerzeichen vor jedes Wort außer dem ersten.
Bei der In-Place-Version nur eine Umkehrung durchführen. Wenn nur die Wörter umgekehrt werden, ergibt sich yddoC snur ni 51 segaugnal.
In PHP und R kann eine Eingabe, die nur aus Ziffern besteht, wie 2026, als Zahl ankommen. Wandle sie vor dem Aufteilen in eine Zeichenkette um.

Häufige Fragen3

Wie hoch ist die Zeitkomplexität von „Reverse Words in a String“?

Beide Ansätze benötigen für einen String der Länge n eine Laufzeit von O(n), da jedes Zeichen eine konstante Anzahl von Malen gelesen und geschrieben wird. Das Aufteilen benötigt O(n) zusätzlichen Speicherplatz für die Wortliste. Das Umkehren des gesamten Strings und anschließend jedes einzelnen Wortes benötigt O(1) zusätzlichen Speicherplatz in einem Zeichenarray, das du bearbeiten kannst.

Wie gehst du mit mehreren Leerzeichen zwischen Wörtern um?

Betrachte ein Wort als eine Folge von Nicht-Leerzeichen-Zeichen und übernimm niemals Leerzeichen aus der Eingabe. Ein Split ohne Trennzeichen in Python und Ruby, strings.Fields in Go und split_whitespace in Rust überspringen bereits jede Folge von Leerzeichen sowie beide Enden; andernorts lässt du die leeren Teile weg. Schreibe dann zwischen die Wörter jeweils ein Leerzeichen.

Kannst du die Wörter ohne eine Split-Funktion umkehren?

Ja. Durchlaufe den Text vom rechten Ende aus: Überspringe Leerzeichen, markiere, wo ein Wort endet, gehe nach links zu seinem Anfang und füge das Wort mit einem Leerzeichen davor an, außer es ist das erste. Jedes Zeichen wird einmal besucht, daher bleibt die Laufzeit bei O(n), und die Wörter kommen in umgekehrter Reihenfolge heraus, ohne dass eine Liste umgekehrt werden muss.

def reverseWords(s):
    # Schreibe hier den Code

Test #1

Test #2

Test #3

Argument

s = "Coddy runs in 15 languages"

Erwartete Ausgabe

"languages 15 in runs Coddy"