String Compression

Q: Qual è la complessità temporale della compressione delle stringhe?

La scansione con due puntatori richiede un tempo O(n) , perché l’indice di scansione si sposta solo in avanti. Oltre al risultato, conserva due indici, quindi lo spazio aggiuntivo è O(1) .

FacileDue puntatori Array e stringhe

+10

Ricevi una stringa s composta da lettere inglesi. Comprimila: sostituisci ogni sequenza di due o più lettere uguali consecutive con quella lettera seguita dalla lunghezza della sequenza, e lascia invariata una lettera isolata. Quindi aabccc diventa a2bc3. Restituisci la stringa compressa.

Le lettere maiuscole e minuscole sono diverse: aA corrisponde a due sequenze di lunghezza 1.

Funzione

compress(s: string) → string

sstring: la stringa da comprimere, solo lettere inglesi
Restituiscestring: la stringa compressa, ogni sequenza rappresentata dalla sua lettera seguita dalla sua lunghezza quando la lunghezza è maggiore di 1

Vincoli

1 ≤ s.length ≤ 2 × 10⁴
s contiene solo lettere inglesi, da a a z e da A a Z.
Una lunghezza di sequenza è scritta in notazione decimale e può avere diverse cifre.

Esempi

Input: s = "aabccc"
Output: "a2bc3"
Spiegazione: Le sequenze sono aa, b e ccc. Diventano a2, b (una lettera singola non riceve alcun conteggio) e c3.

Input: s = "abbbbbbbbbbbb"
Output: "ab12"
Spiegazione: Una a, poi dodici b. La lunghezza 12 è scritta con i due caratteri 1 e 2, quindi il risultato è ab12.

Input: s = "zzZZZ"
Output: "z2Z3"
Spiegazione: La z minuscola e la Z maiuscola sono lettere diverse, quindi questa è una sequenza di due seguita da una sequenza di tre: z2Z3.

Per approfondire

Scrivi l’operazione inversa: data una stringa compressa come ab12, ricostruisci l’originale. Come leggi un conteggio composto da più cifre?

Suggerimenti

Aprili uno alla volta. Ognuno rivela un po’ di più.

0 di 3 aperti

Soluzione

Trova dove inizia e finisce ogni sequenza di lettere uguali, poi scrivine la lunghezza come testo. Una sequenza di una sola lettera non riceve alcun conteggio, e un conteggio può avere più cifre. Due indici, uno all’inizio di una sequenza e l’altro che scorre fino alla sua fine, lo fanno in un solo passaggio.

Raccogli i tratti, poi scrivili

Intuizione

Per prima cosa registra le sequenze come coppie di una lettera e una lunghezza: per aabccc, (a, 2), (b, 1), (c, 3). Ogni lettera estende l'ultima sequenza oppure ne avvia una nuova. Poi scrivi la lettera di ogni sequenza, seguita dalla sua lunghezza quando è maggiore di 1.

Entrambi i passaggi richiedono O(n). La lista può contenere n sequenze quando non ci sono due caratteri adiacenti uguali, quindi richiede O(n) spazio aggiuntivo.

Algoritmo

Crea una lista vuota di sequenze.
Per ogni lettera di s: se l'ultima sequenza ha la stessa lettera, aggiungi 1 alla sua lunghezza; altrimenti aggiungi una nuova sequenza di lunghezza 1.
Per ogni sequenza, scrivi la sua lettera, poi la sua lunghezza in formato decimale se la lunghezza è maggiore di 1.

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)

Due puntatori per ciascun blocco

Intuizione

Mantieni i sulla prima lettera del gruppo corrente e fai avanzare j finché s[j] è uguale a s[i]. Quando j si ferma, davanti a una lettera diversa o alla fine, la lunghezza del gruppo è j-i. Scrivila e imposta i = j. In abbbbbbbbbbbb, j si ferma prima a 1, producendo a, poi a 13, producendo b12.

L'ultimo gruppo non richiede un caso speciale, perché il ciclo interno si ferma alla fine della stringa. j avanza soltanto, quindi il tempo è O(n) e, oltre al risultato, mantieni due indici. Le versioni in R e Swift suddividono prima s in un array di caratteri, quindi usano O(n) spazio aggiuntivo.

Algoritmo

Imposta i = 0.
Mentre i si trova all’interno della stringa, imposta j = i e fai avanzare j finché si trova all’interno della stringa e s[j] è uguale a s[i].
Scrivi s[i]; se j-i è maggiore di 1, scrivilo come testo decimale.
Imposta i = j e ripeti.

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)

Trappole e casi limite

Scrivere una sequenza solo quando incontri una lettera diversa. Dopo l'ultimo ccc di aabccc non c'è niente, quindi restituisci a2b.
Scrivere il conteggio con un solo carattere, ad esempio '0' + count. Si interrompe a 10: dodici b richiedono i due caratteri 12.
Scrivere 1 dopo una lettera singola. b resta b, non b1.
Ignorare le maiuscole e le minuscole. zzZZZ è z2Z3, non z5.
Far crescere una stringa immutabile con +, come in Java o C#. Ogni + copia il risultato ottenuto finora, rendendo il ciclo O(n²); usa un generatore di stringhe.

Domande frequenti3

Qual è la complessità temporale della compressione delle stringhe?

La scansione con due puntatori richiede un tempo O(n), perché l’indice di scansione si sposta solo in avanti. Oltre al risultato, conserva due indici, quindi lo spazio aggiuntivo è O(1).

La stringa compressa può essere più lunga dell'originale?

Non in questa versione. Una singola lettera rimane un carattere e una sequenza di k ≥ 2 lettere diventa una lettera più le cifre di k, mai più di k caratteri. Uno schema che scrive un conteggio dopo ogni lettera, come a1b1, può raddoppiare la lunghezza.

Come si comprime una stringa sul posto?

Usa un array di caratteri con un indice di lettura e un indice di scrittura. Esamina ogni sequenza con l’indice di lettura, poi scrivi la sua lettera e le cifre della sua lunghezza all’indice di scrittura. L’output non è mai più lungo dell’input letto fino a quel momento, quindi l’indice di scrittura non supera mai quello di lettura. Restituisci la nuova lunghezza alla fine.

def compress(s):
    # Scrivi il codice qui

Test #1

Test #2

Test #3

Argomento

s = "aabccc"

Output atteso

"a2bc3"