String Compression

Q: Wie hoch ist die Zeitkomplexität der String-Komprimierung?

Der Zwei-Zeiger-Durchlauf benötigt O(n) Zeit, da sich der Scan-Index nur vorwärts bewegt. Abgesehen vom Ergebnis speichert er zwei Indizes, daher beträgt der zusätzliche Speicherbedarf O(1) .

LeichtZwei Zeiger Arrays und Strings

+10

Du erhältst eine Zeichenfolge s aus englischen Buchstaben. Komprimiere sie: Ersetze jede Folge von zwei oder mehr gleichen Buchstaben hintereinander durch diesen Buchstaben, gefolgt von der Länge der Folge, und lasse einen einzelnen Buchstaben unverändert. So wird aabccc zu a2bc3. Gib die komprimierte Zeichenfolge zurück.

Groß- und Kleinbuchstaben sind unterschiedliche Buchstaben: aA besteht aus zwei Folgen der Länge 1.

Funktion

compress(s: string) → string

sstring: die zu komprimierende Zeichenfolge, nur englische Buchstaben
Gibt zurückstring: die komprimierte Zeichenfolge, wobei jede Folge als ihr Buchstabe gefolgt von ihrer Länge geschrieben wird, wenn die Länge größer als 1 ist

Einschränkungen

1 ≤ s.length ≤ 2 × 10⁴
s enthält nur englische Buchstaben, a bis z und A bis Z.
Eine Lauflänge wird dezimal geschrieben und kann mehrere Ziffern haben.

Beispiele

Eingabe: s = "aabccc"
Ausgabe: "a2bc3"
Erklärung: Die Folgen sind aa, b und ccc. Sie werden zu a2, b (ein einzelner Buchstabe erhält keine Anzahl) und c3.

Eingabe: s = "abbbbbbbbbbbb"
Ausgabe: "ab12"
Erklärung: Ein a, dann zwölf bs. Die Länge 12 wird als die beiden Zeichen 1 und 2 geschrieben, daher lautet das Ergebnis ab12.

Eingabe: s = "zzZZZ"
Ausgabe: "z2Z3"
Erklärung: Kleinbuchstabe z und Großbuchstabe Z sind unterschiedliche Buchstaben, also ist dies eine Folge von zwei, gefolgt von einer Folge von drei: z2Z3.

Weiterführende Frage

Schreibe die Umkehrung: Rekonstruiere aus einer komprimierten Zeichenfolge wie ab12 das Original. Wie liest du eine Anzahl, die aus mehreren Ziffern besteht?

Tipps

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

0 von 3 geöffnet

Lösung

Finde heraus, wo jede Folge gleicher Buchstaben beginnt und endet, und schreibe dann ihre Länge als Text auf. Eine Folge aus nur einem Buchstaben erhält keine Anzahl, und eine Anzahl kann aus mehreren Ziffern bestehen. Zwei Indizes, einer am Anfang einer Folge und einer, der bis zu ihrem Ende weiterläuft, erledigen das in einem Durchgang.

Sammle die Läufe und schreibe sie dann auf

Idee

Erfasse zuerst die Läufe als Paare aus einem Buchstaben und einer Länge: für aabccc also (a, 2), (b, 1), (c, 3). Jeder Buchstabe verlängert entweder den letzten Lauf oder beginnt einen neuen. Schreibe dann den Buchstaben jedes Laufs und danach seine Länge, wenn sie größer als 1 ist.

Beide Durchläufe benötigen O(n). Wenn keine zwei benachbarten Buchstaben übereinstimmen, kann die Liste n Läufe enthalten; sie benötigt also zusätzlich O(n) Speicherplatz.

Algorithmus

Erstelle eine leere Liste von Läufen.
Für jeden Buchstaben von s: Wenn der letzte Lauf denselben Buchstaben enthält, erhöhe seine Länge um 1; andernfalls füge einen neuen Lauf der Länge 1 hinzu.
Schreibe für jeden Lauf seinen Buchstaben und anschließend seine Länge als Dezimalzahl, wenn die Länge größer als 1 ist.

def compress(s):
    # First pass: collect the runs as [letter, length] pairs
    runs = []
    for ch in s:
        if runs and runs[-1][0] == ch:
            runs[-1][1] += 1
        else:
            runs.append([ch, 1])
    # Second pass: write each run, with its length when it is more than 1
    parts = []
    for letter, length in runs:
        parts.append(letter)
        if length > 1:
            parts.append(str(length))
    return "".join(parts)

Zwei Zeiger über jeden Durchlauf

Idee

Lass i beim ersten Buchstaben des aktuellen Laufs stehen und bewege j weiter, solange s[j] gleich s[i] ist. Wenn j bei einem anderen Buchstaben oder am Ende anhält, ist die Länge des Laufs j-i. Gib sie aus und setze i = j. Bei abbbbbbbbbbbb hält j zuerst bei 1 an und ergibt a, dann bei 13 und ergibt b12.

Der letzte Lauf benötigt keinen Sonderfall, da die innere Schleife am Ende der Zeichenfolge anhält. j bewegt sich nur vorwärts, daher beträgt die Laufzeit O(n), und zusätzlich zum Ergebnis speicherst du zwei Indizes. Die R- und Swift-Versionen teilen s zuerst in ein Zeichenarray auf, daher benötigen sie zusätzlichen Speicherplatz von O(n).

Algorithmus

Setze i = 0.
Solange i innerhalb der Zeichenkette liegt, setze j = i und erhöhe j, solange es innerhalb der Zeichenkette liegt und s[j] gleich s[i] ist.
Gib s[i] aus; wenn j-i größer als 1 ist, gib es als Dezimalzahl aus.
Setze i = j und wiederhole den Vorgang.

def compress(s):
    parts = []
    n = len(s)
    i = 0
    while i < n:
        # Move j to the first index after the run that starts at i
        j = i
        while j < n and s[j] == s[i]:
            j += 1
        parts.append(s[i])
        if j - i > 1:
            parts.append(str(j - i))
        i = j
    return "".join(parts)

Stolperfallen und Grenzfälle

Einen Lauf nur zu schreiben, wenn du auf einen anderen Buchstaben triffst. Auf das letzte ccc in aabccc folgt nichts, also gibst du a2b zurück.
Die Anzahl als ein Zeichen zu schreiben, etwa '0' + count. Bei 10 funktioniert das nicht mehr: Für zwölf bs brauchst du die beiden Zeichen 12.
Nach einem einzelnen Buchstaben 1 zu schreiben. b bleibt b, nicht b1.
Die Groß- und Kleinschreibung zu ignorieren. zzZZZ ist z2Z3, nicht z5.
Einen unveränderlichen String mit + zu erweitern, wie in Java oder C#. Jedes + kopiert das bisherige Ergebnis, wodurch die Schleife eine Laufzeit von O(n²) hat; verwende einen StringBuilder.

Häufige Fragen3

Wie hoch ist die Zeitkomplexität der String-Komprimierung?

Der Zwei-Zeiger-Durchlauf benötigt O(n) Zeit, da sich der Scan-Index nur vorwärts bewegt. Abgesehen vom Ergebnis speichert er zwei Indizes, daher beträgt der zusätzliche Speicherbedarf O(1).

Kann die komprimierte Zeichenfolge länger als das Original sein?

Nicht in dieser Version. Ein einzelner Buchstabe bleibt ein Zeichen, und eine Folge von k ≥ 2 Buchstaben wird zu einem Buchstaben plus den Ziffern von k, niemals länger als k Zeichen. Ein Schema, das nach jedem Buchstaben eine Anzahl schreibt, etwa a1b1, kann die Länge verdoppeln.

Wie komprimiert man eine Zeichenfolge direkt an ihrem Speicherort?

Verwende ein Zeichenarray mit einem Leseindex und einem Schreibindex. Durchlaufe jeden zusammenhängenden Abschnitt mit dem Leseindex und schreibe dann seinen Buchstaben und die Ziffern seiner Länge an den Schreibindex. Die Ausgabe ist nie länger als die bisher gelesene Eingabe, daher überholt der Schreibindex den Leseindex nie. Gib am Ende die neue Länge zurück.

def compress(s):
    # Schreibe hier Code

Test #1

Test #2

Test #3

Argument

s = "aabccc"

Erwartete Ausgabe

"a2bc3"