Decode String

Q: Perché lo stack memorizza il testo che precedeva ogni parentesi?

Quando si apre una [ , il testo decodificato finora a quel livello non è completo: le copie del gruppo devono ancora essere aggiunte dopo. Inserirlo nello stack lo mantiene al sicuro mentre decodifichi il corpo partendo da una stringa vuota. Quando arriva la ] corrispondente, estrarlo dallo stack ti restituisce quel testo e puoi aggiungervi le copie.

MedioStack Ricorsione

+10

Una stringa codificata rappresenta il testo ripetuto come k[text], che indica text scritto k volte di seguito. I gruppi possono trovarsi all'interno di altri gruppi, quindi 2[a3[b]] indica abbbabbb. Scrivi una funzione che riceve una stringa codificata s e restituisce la stringa decodificata.

Le lettere che si trovano fuori da tutte le parentesi restano invariate. Ogni conteggio è un numero intero positivo scritto subito prima della sua [ e le cifre non compaiono in nessun altro punto.

Funzione

decodeString(s: string) → string

sstring: la stringa codificata
Restituiscestring: la stringa decodificata

Vincoli

1 ≤ s.length ≤ 10⁴
s contiene solo lettere inglesi minuscole, cifre, [ e ].
s è una codifica valida: ogni [ è preceduta da un conteggio e ha una ] corrispondente, e nessuna parentesi è vuota.
Ogni conteggio k soddisfa 1 ≤ k ≤ 300 e non ha zeri iniziali.
Le parentesi possono essere annidate fino a un massimo di 100 livelli.
La stringa decodificata contiene al massimo 5 × 10⁴ caratteri.

Esempi

Input: s = "2[ab]3[c]x"
Output: "ababcccx"
Spiegazione: 2[ab] dà abab e 3[c] dà ccc. La x si trova fuori da tutte le parentesi, quindi viene copiata così com'è, ottenendo ababcccx.

Input: s = "2[x3[yz]]"
Output: "xyzyzyzxyzyzyz"
Spiegazione: Decodifica prima la parte interna: 3[yz] è yzyzyz, quindi il contenuto del gruppo esterno è xyzyzyz. Scritto due volte, diventa xyzyzyzxyzyzyz.

Input: s = "q10[w]e"
Output: "qwwwwwwwwwwe"
Spiegazione: Il conteggio è 10, letto da due cifre, quindi w compare dieci volte tra q ed e. Il codice che legge solo la cifra accanto a [ lo ripeterebbe 0 volte.

+22 test nascosti all’invio

Per approfondire

La stringa decodificata può essere molto più lunga dell'input. Come restituiresti solo il carattere nella posizione i della stringa decodificata, senza crearla, quando la sua lunghezza può arrivare a 10^18?

Suggerimenti

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

0 di 3 aperti

Soluzione

Il conteggio viene prima delle parentesi, ma non puoi scrivere le copie finché non sai cosa c'è al loro interno, e al loro interno possono esserci altri gruppi. Quindi un gruppo può essere espanso solo quando tutti i gruppi al suo interno sono completati. Ogni approccio qui sotto è un modo per completare prima i gruppi più interni: riscrivere la stringa dall'interno verso l'esterno, lasciare che una chiamata ricorsiva completi il gruppo interno prima di quello esterno oppure mantenere i gruppi esterni incompleti su uno stack. Qui sotto, n è la lunghezza dell'input, m la lunghezza della stringa decodificata e d la profondità massima di annidamento.

Espandi il gruppo più interno, poi ripeti

Intuizione

Decodifica la stringa come faresti su carta. Trova un gruppo che non ne contenga altri, scrivi al suo posto le sue copie e ricontrolla. In 2[x3[yz]], il gruppo 3[yz] non contiene nulla, quindi la stringa diventa 2[xyzyzyz] e un'altra espansione dà la risposta.

Il primo ] nella stringa chiude sempre un gruppo di questo tipo. Nessun altro gruppo si è chiuso prima, quindi niente tra questo carattere e il suo [ può essere una parentesi quadra. Quel [ è il più vicino alla sua sinistra, e il conteggio è la sequenza di cifre immediatamente precedente. Sostituisci il conteggio, le parentesi e il contenuto con il contenuto ripetuto k volte, e ripeti finché non resta alcun ].

Questo è corretto, ma a ogni espansione l'intera stringa viene ricostruita. Con b gruppi e una stringa che cresce fino a m caratteri, si copiano fino a b × m caratteri. Il test nascosto con circa 1,300 gruppi affiancati richiede circa 25 milioni di copie per produrre 27,688 caratteri, mentre basterebbe un passaggio sull'input.

Algoritmo

Trova il primo ] nella stringa. Se non c'è, la stringa è decodificata: restituiscila.
Procedi verso sinistra da esso fino alla [ più vicina. Il testo tra le due parentesi è il corpo del gruppo.
Procedi ancora verso sinistra oltre le cifre prima di quella [ e leggile come conteggio k.
Sostituisci tutto dalla prima cifra fino a ] con il corpo ripetuto k volte.
Torna al passaggio 1.

def decodeString(s):
    # Expand one innermost group at a time until no bracket is left.
    while True:
        close = s.find("]")
        if close == -1:
            return s
        # The first ']' closes a group with no group inside it,
        # and the nearest '[' to its left opens that group.
        open_ = s.rfind("[", 0, close)
        start = open_
        while start > 0 and s[start - 1].isdigit():
            start -= 1
        times = int(s[start:open_])
        s = s[:start] + s[open_ + 1:close] * times + s[close + 1:]

Discesa ricorsiva

Intuizione

Il formato è ricorsivo: una stringa codificata è una sequenza di lettere e gruppi, e il corpo di un gruppo è a sua volta una stringa codificata. Quindi scrivi una funzione, decode, che legga da una posizione condivisa finché non raggiunge il ] che termina il suo livello o la fine dell’input, e restituisca ciò che ha letto, decodificato.

Quando decode incontra una cifra, legge l’intero numero, salta [ e richiama sé stessa per decodificare il corpo. La chiamata si ferma alla ] corrispondente, perché ogni ] più interno è già stato consumato da una chiamata più profonda. La chiamata chiamante salta la ], aggiunge il corpo k volte e continua a leggere. Per 2[x3[yz]], la chiamata esterna legge 2; la chiamata successiva legge x e 3; una terza chiamata restituisce yz; la chiamata intermedia restituisce xyzyzyz; e quella esterna lo scrive due volte.

Ogni carattere dell’input viene letto una volta. Il costo effettivo è la copia: un carattere dell’output viene copiato una volta per ogni gruppo che lo contiene, quindi il tempo è O(n + m·d) per una profondità di annidamento d. Anche la ricorsione raggiunge una profondità di d chiamate. Va bene per 100 livelli, ma un input molto profondo può causare un overflow dello stack delle chiamate: Python, per esempio, si ferma per impostazione predefinita a 1.000 chiamate annidate.

Algoritmo

Mantieni una posizione pos, condivisa da ogni chiamata, che inizia dal primo carattere.
decode() esegue un ciclo mentre pos si trova all'interno della stringa e non è su un ].
Quando trovi una lettera, aggiungila e prosegui.
Quando trovi una cifra, leggi l'intero numero k, salta [, chiama decode() per il contenuto, salta ] e aggiungi il contenuto k volte.
Restituisci ciò che hai costruito. La prima chiamata restituisce la stringa decodificata.

def decodeString(s):
    pos = 0

    def decode():
        # Read from pos up to the ']' that closes this level, or the end.
        nonlocal pos
        parts = []
        while pos < len(s) and s[pos] != "]":
            if s[pos].isdigit():
                times = 0
                while s[pos].isdigit():
                    times = times * 10 + int(s[pos])
                    pos += 1
                pos += 1          # skip '['
                inner = decode()  # the group's body, fully decoded
                pos += 1          # skip ']'
                parts.append(inner * times)
            else:
                parts.append(s[pos])
                pos += 1
        return "".join(parts)

    return decode()

Un passaggio con uno stack

Intuizione

La ricorsione conserva una porzione di testo incompleta per ogni gruppo aperto nei suoi frame di chiamata. Puoi invece conservare queste porzioni in una pila e leggere la stringa in un unico ciclo.

Tieni traccia di due elementi per il livello corrente: current, il testo decodificato finora, e count, il numero che si sta leggendo. Una cifra estende count come count × 10 + digit, così 10 e 300 vengono elaborati correttamente. Una [ apre un livello: inserisci current e count nella pila, poi azzera entrambi. Una lettera viene aggiunta a current. Una ] chiude il livello: estrai dalla pila il testo salvato e il conteggio, e current diventa il testo salvato seguito da count copie di current.

Segui 2[x3[yz]]. Alla prima [ inserisci (vuoto, 2) nella pila. La x fa sì che current diventi x. Alla seconda [ inserisci (x, 3) nella pila, e yz riempie un nuovo current. Al primo ] estrai (x, 3), quindi current diventa xyzyzyz. All’ultimo ] estrai (vuoto, 2) e current diventa xyzyzyzxyzyzyz.

I gruppi si chiudono nell’ordine inverso a quello in cui si aprono, quindi la cima della pila è sempre il livello a cui ] ritorna. Il lavoro richiesto è pari a quello della ricorsione, O(n + m·d), ma un annidamento profondo fa crescere solo una lista, mai lo stack delle chiamate.

Algoritmo

Inizia con una pila vuota, una stringa current vuota e count = 0.
Quando trovi una cifra, imposta count = count × 10 + digit.
Quando trovi [, inserisci la coppia (current, count) nella pila, poi reimposta current come vuota e count a 0.
Quando trovi una lettera, aggiungila a current.
Quando trovi ], estrai (before, k) e imposta current su before seguito da k copie di current.
Dopo l’ultimo carattere, restituisci current.

def decodeString(s):
    stack = []      # one entry per open '[': (the text before it, its count)
    current = []    # pieces of the text at the current level
    count = 0
    for ch in s:
        if ch.isdigit():
            count = count * 10 + int(ch)   # counts can have several digits
        elif ch == "[":
            stack.append((current, count))
            current, count = [], 0
        elif ch == "]":
            before, times = stack.pop()
            before.append("".join(current) * times)
            current = before
        else:
            current.append(ch)
    return "".join(current)

Trappole e casi limite

La maggior parte delle risposte errate deriva dalla lettura del conteggio o da dove viene inserito il testo salvato.

Leggere una sola cifra come conteggio completo. In q10[w]e il conteggio è 10. Il codice che prende solo la cifra prima di [ ripete w 0 volte.
Dimenticare di reimpostare count a 0 dopo averlo inserito. Le cifre del gruppo successivo vengono quindi aggiunte al numero precedente, perciò 2[a3[b]] legge il conteggio interno come 23.
Inserire le copie prima del testo salvato. In corrispondenza di una ], il risultato è il testo precedente al gruppo seguito dalle copie, quindi ab2[c] diventa abcc, non ccab.
Perdere lettere al livello più esterno. La x in 2[ab]3[c]x è fuori da tutte le parentesi e fa comunque parte della risposta.
Aggiungere un carattere alla volta a una stringa immutabile lunga. Ogni aggiunta può copiare l'intera stringa, trasformando una risposta di 50,000 caratteri in miliardi di copie. Raccogli i pezzi in una lista o in un generatore di stringhe.

Domande frequenti4

Qual è la complessità temporale di Decode String?

La lettura dell'input è O(n). La creazione dell'output copia ogni carattere una volta per ogni gruppo in cui si trova, quindi il totale è O(n + m·d), dove m è la lunghezza decodificata e d la profondità di annidamento. Quando ogni conteggio è almeno 2, ogni gruppo è lungo al massimo la metà del gruppo che lo racchiude, quindi il numero di copie rimane inferiore a 2m. Nessun approccio può essere più efficiente di O(m), perché la risposta stessa contiene m caratteri.

Dovresti risolvere Decode String con la ricorsione o con uno stack?

Entrambi svolgono lo stesso lavoro. La ricorsione segue direttamente il formato, poiché il corpo di un gruppo è a sua volta una stringa codificata, e spesso è il modo più veloce da scrivere durante un colloquio. La versione con lo stack fa la stessa cosa in un unico ciclo e mantiene i livelli esterni incompleti in una lista, così un annidamento molto profondo non può causare l'overflow dello stack delle chiamate. Se l'intervistatore chiede come gestire un input annidato a migliaia di livelli di profondità, la risposta è lo stack.

Come gestisci i conteggi con più di una cifra?

Costruisci il numero man mano che lo leggi: parti da 0 e, per ogni cifra, imposta count = count × 10 + digit. Quando arriva [, il numero è completo, quindi 300[a] dà 300. Reimposta count a 0 non appena lo inserisci, altrimenti le cifre del gruppo successivo si aggiungeranno a esso.

Perché lo stack memorizza il testo che precedeva ogni parentesi?

Quando si apre una [, il testo decodificato finora a quel livello non è completo: le copie del gruppo devono ancora essere aggiunte dopo. Inserirlo nello stack lo mantiene al sicuro mentre decodifichi il corpo partendo da una stringa vuota. Quando arriva la ] corrispondente, estrarlo dallo stack ti restituisce quel testo e puoi aggiungervi le copie.

Python

def decodeString(s):
    # Scrivi il codice qui

Casi di test

Caso 1

Caso 2

Caso 3

Input

s = "2[ab]3[c]x"

Atteso

"ababcccx"

Decode String

Funzione

Vincoli

Esempi

Suggerimenti

Soluzione

Espandi il gruppo più interno, poi ripeti

Discesa ricorsiva

Un passaggio con uno stack

Trappole e casi limite

Domande frequenti4

Problemi simili