Decode Ways

Q: Come si gestiscono gli zeri in Decode Ways?

Uno 0 non può mai essere una lettera da solo, quindi deve essere abbinato alla cifra che lo precede; solo 10 e 20 sono codici. Nel ciclo dal basso verso l’alto, ciò significa che uno 0 non aggiunge nulla nel caso a una cifra e aggiunge il conteggio di due cifre prima solo dopo un 1 o un 2. Uno 0 iniziale, due zeri consecutivi o uno 0 dopo una cifra da 3 a 9 fanno sì che la risposta sia 0.

MedioProgrammazione dinamica

+10

Un messaggio composto da lettere maiuscole è stato convertito in cifre con il codice A = 1, B = 2 e così via fino a Z = 26, e i codici sono stati scritti uno dopo l’altro senza separatori. Hai la stringa di cifre s. Restituisci il numero di messaggi diversi che potrebbero averla generata.

Ogni lettera si legge da una cifra o da due cifre adiacenti, e un codice non inizia mai con 0: 06 non è 6 e uno 0 da solo non è una lettera. Se nessuna lettura funziona, restituisci 0.

Funzione

numDecodings(s: string) → integer

sstring: la stringa di cifre da decodificare
Restituisceinteger: il numero di messaggi di lettere che codificano s

Vincoli

1 ≤ s.length ≤ 100
s contiene solo le cifre da 0 a 9 e può iniziare con 0.
Ogni prefisso e ogni suffisso di s ha meno di 2³¹ interpretazioni, quindi la risposta e ogni conteggio che calcoli lungo il percorso rientrano in un intero con segno a 32 bit.

Esempi

Input: s = "2611"
Output: 4
Spiegazione: Le quattro letture sono 2 6 1 1 (BFAA), 26 1 1 (ZAA), 2 6 11 (BFK) e 26 11 (ZK). Le cifre centrali non si accoppiano mai, perché 61 è maggiore di 26.

Input: s = "1203"
Output: 1
Spiegazione: Lo 0 deve essere abbinato al 2 che lo precede per formare 20, il che impone la lettura 1 20 3 (ATC). Leggere prima 12 lascerebbe lo 0 da solo, e 03 inizia con 0.

Input: s = "06"
Output: 0
Spiegazione: La prima lettera dovrebbe iniziare con 0. Uno 0 da solo non è una lettera e 06 non è un codice, quindi nessun messaggio fornisce questa stringa.

+25 test nascosti all’invio

Per approfondire

E se s potesse contenere anche *, che rappresenta qualsiasi cifra da 1 a 9? Riesci a contare le letture in tempo O(n), restituendo il conteggio modulo 10^9+7?

Suggerimenti

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

0 di 3 aperti

Soluzione

Ogni cifra è una lettera a sé oppure si unisce alla cifra vicina formando una lettera di due cifre, quindi il numero di letture cresce come i numeri di Fibonacci: 45 cifre 1 ne hanno già 1836311903. Elencare le letture è impossibile. Ciò che risolve il problema è che il numero di modi per completare una lettura dipende solo dalla posizione raggiunta, quindi occorre contare ogni posizione una sola volta. È con gli zeri che bisogna fare attenzione: un 0 può essere solo la seconda cifra di 10 o 20.

Prova entrambe le interpretazioni con la ricorsione

Corretto, ma non termina sui test più grandi

Intuizione

Posizionati all'indice i e guarda la cifra successiva. Se è 0, qui non inizia nessuna lettera e questo percorso non produce alcuna lettura. Altrimenti puoi leggere quella cifra come una lettera e contare le letture del resto a partire da i+1. Se insieme alla cifra successiva forma un numero da 10 a 26, puoi anche leggere entrambe come un'unica lettera e contare a partire da i+2. Le due scelte danno lettere iniziali diverse, quindi i loro conteggi si sommano senza sovrapporsi. Quando i raggiunge la fine della stringa, hai completato una lettura, quindi restituisci 1.

Per "2611": la prima lettera è 2 oppure 26. Dopo 2, la lettera successiva deve essere 6, perché 61 è troppo grande. Entrambi i rami terminano poi con 1 1 oppure 11, quindi il totale è 2 × 2 = 4.

La risposta è corretta, ma non viene memorizzato nulla. Con una stringa di 1, ogni chiamata si ramifica in due e le chiamate seguono la regola di Fibonacci, quindi 45 cifre 1 richiedono circa 5 × 10^9 chiamate. Il lavoro non diminuisce nemmeno insieme alla risposta: con 44 cifre 1 seguite da 55 cifre 3 e uno 0 finale, la risposta è 0, eppure la ricorsione percorre ogni lettura delle cifre 1 attraverso tutte le cifre 3 prima che ogni percorso termini all'ultima cifra, per circa 10^11 chiamate.

Algoritmo

Scrivi una funzione helper waysFrom(i) che conta le letture delle cifre dall’indice i fino alla fine.
Se i è uguale alla lunghezza di s, restituisci 1.
Se la cifra in posizione i è 0, restituisci 0.
Inizia con waysFrom(i+1), le letture in cui la lettera successiva corrisponde a una cifra.
Se le cifre i e i+1 formano un numero al massimo pari a 26, aggiungi waysFrom(i+2). Restituisci waysFrom(0).

def numDecodings(s):
    n = len(s)

    def ways_from(i):
        # The number of ways to decode s[i:].
        if i == n:
            return 1  # nothing left: one finished reading
        if s[i] == "0":
            return 0  # no letter code starts with 0
        ways = ways_from(i + 1)  # read one digit
        if i + 1 < n and int(s[i:i + 2]) <= 26:
            ways += ways_from(i + 2)  # read two digits, 10 to 26
        return ways

    return ways_from(0)

Ricorsione con memo

Intuizione

La ricorsione pone la stessa domanda più e più volte. In "11111", il conteggio dall’indice 3 serve dopo 1 1 1, dopo 11 1 e dopo 1 11, e il risultato è sempre lo stesso, perché dipende solo dalle cifre dall’indice 3 in poi. Memorizza ogni conteggio in un array memo la prima volta che lo calcoli, poi leggilo da lì.

Contrassegna gli slot non ancora calcolati con -1, non con 0. Qui zero è una risposta valida: in una stringa che termina con 30, ogni posizione ha 0 letture. Con 0 come contrassegno, quelle posizioni sembrano sconosciute a ogni visita e la ricorsione è lenta come prima.

Ci sono n posizioni e ognuna viene calcolata una sola volta con un lavoro costante, quindi il tempo è O(n). La memo e lo stack delle chiamate occupano entrambi O(n) spazio. Qui le chiamate si annidano al massimo per 100 livelli, una profondità gestita da qualsiasi linguaggio.

Algoritmo

Crea un array memo con uno slot per ogni indice, tutti impostati a -1.
In waysFrom(i), restituisci 1 alla fine della stringa e memo[i] quando non è -1.
Altrimenti conta come nella ricorsione semplice: 0 per uno 0, altrimenti waysFrom(i+1) più waysFrom(i+2) quando le due cifre formano un numero da 10 a 26.
Salva il conteggio in memo[i], anche se è zero, e restituiscilo.
Restituisci waysFrom(0).

def numDecodings(s):
    n = len(s)
    memo = [-1] * n  # memo[i]: ways to decode s[i:], -1 until worked out

    def ways_from(i):
        if i == n:
            return 1
        if memo[i] != -1:
            return memo[i]
        ways = 0
        if s[i] != "0":
            ways = ways_from(i + 1)  # read one digit
            if i + 1 < n and int(s[i:i + 2]) <= 26:
                ways += ways_from(i + 2)  # read two digits, 10 to 26
        memo[i] = ways
        return ways

    return ways_from(0)

Dal basso verso l’alto con due contatori

Intuizione

Inverti la ricorsione e conta i prefissi. Sia ways(i) il numero di decodifiche delle prime i cifre. L’ultima lettera di una simile decodifica è o la cifra all’indice i-1 da sola, che deve essere una cifra da 1 a 9 e lascia ways(i-1) decodifiche per il resto, oppure le due cifre agli indici i-2 e i-1, che devono formare un numero da 10 a 26 e lasciano ways(i-2) decodifiche. Quindi ways(i) è la somma delle parti la cui condizione è soddisfatta. Il prefisso vuoto ha una decodifica, il messaggio vuoto, quindi ways(0) = 1.

Considera "1203". Dopo 1 il conteggio è 1. Dopo 12 è 2: 1 2 e 12. Lo 0 non può comparire da solo e funziona solo 20, quindi il conteggio torna a quello precedente al 2, che è 1. Il 3 compare da solo e 03 non è un codice, quindi il conteggio resta 1.

Ogni conteggio considera solo i due conteggi precedenti, quindi due variabili, twoBack e oneBack, sostituiscono la tabella. Si tratta di un’unica passata con lavoro costante per ogni cifra: tempo O(n), spazio O(1) e nessuna ricorsione.

Algoritmo

Imposta twoBack = 0 e oneBack = 1, il conteggio per il prefisso vuoto.
Per ogni indice i, inizializza current a 0 e aggiungi oneBack se la cifra i non è 0.
Se i ≥ 1, la cifra i-1 non è 0 e le cifre i-1 e i formano un numero al massimo pari a 26, aggiungi twoBack.
Fai avanzare: twoBack = oneBack, poi oneBack = current.
Dopo l'ultima cifra, restituisci oneBack.

def numDecodings(s):
    # ways(i) counts the readings of the first i digits; ways(0) = 1.
    two_back, one_back = 0, 1  # ways(i-1) and ways(i) before digit i is read
    for i in range(len(s)):
        current = 0
        if s[i] != "0":
            current = one_back  # digit i is a letter on its own
        if i >= 1 and s[i - 1] != "0" and int(s[i - 1:i + 1]) <= 26:
            current += two_back  # digits i-1 and i form one letter, 10 to 26
        two_back, one_back = one_back, current
    return one_back

Trappole e casi limite

Quasi tutte le risposte sbagliate a questo problema dipendono dagli zeri o da una memoizzazione che dimentica.

Considerare 0 una lettera o 06 come 6. Uno zero può completare solo 10 o 20, quindi "30", "100" e "06" hanno tutti 0 decodifiche.
Verificare solo che una coppia di cifre sia ≤ 26. 05 vale 5 come numero, ma non è un codice. Controlla che la prima delle due cifre non sia 0.
Usare 0 come contrassegno per uno slot della memoizzazione non ancora calcolato. Molte posizioni hanno davvero 0 decodifiche, quindi questi slot non vengono mai considerati memorizzati e vengono ricalcolati a ogni visita. Con 44 cifre 1 seguite da cifre 3 e uno 0 finale, ogni slot vale 0 e si torna a circa 10^11 chiamate.
Leggere la cifra prima dell'indice 0. Proteggi il controllo delle due cifre con i ≥ 1: in Python s[-1] legge silenziosamente l'ultima cifra, mentre altri linguaggi leggono al di fuori della stringa.
Convertire s in un unico numero. Cento cifre non entrano in alcun tipo intero, e la conversione elimina gli zeri iniziali, che modificano la risposta. Procedi cifra per cifra.
In Lua e R, le posizioni iniziano da 1, quindi la fine della stringa è alla posizione n+1 e il primo controllo di due cifre si trova alla posizione 2.

Domande frequenti4

Qual è la complessità temporale di Decode Ways?

La soluzione bottom-up legge ogni cifra una sola volta con un lavoro costante, quindi ha un tempo di esecuzione O(n) e usa O(1) spazio aggiuntivo. Anche la ricorsione con memoizzazione ha un tempo di esecuzione O(n), ma usa O(n) spazio per la memo e lo stack delle chiamate. La ricorsione semplice è esponenziale: su una stringa di uno, il numero di chiamate cresce come 1.618^n.

In che modo Decode Ways è correlato a Climbing Stairs?

Entrambi contano i modi per coprire una linea con passi di dimensione 1 e 2. In Climbing Stairs ogni passo è consentito, quindi il conteggio è un numero di Fibonacci. In Decode Ways, per un passo di una cifra serve una cifra da 1 a 9 e per un passo di due cifre serve un numero da 10 a 26, quindi ogni termine della somma viene aggiunto solo quando la sua condizione è soddisfatta. Una stringa di uno consente ogni passo e i suoi conteggi sono esattamente i numeri di Fibonacci.

Come si gestiscono gli zeri in Decode Ways?

Uno 0 non può mai essere una lettera da solo, quindi deve essere abbinato alla cifra che lo precede; solo 10 e 20 sono codici. Nel ciclo dal basso verso l’alto, ciò significa che uno 0 non aggiunge nulla nel caso a una cifra e aggiunge il conteggio di due cifre prima solo dopo un 1 o un 2. Uno 0 iniziale, due zeri consecutivi o uno 0 dopo una cifra da 3 a 9 fanno sì che la risposta sia 0.

È possibile risolvere Decodifica dei modi con spazio O(1)?

Sì. Il conteggio di un prefisso dipende solo dai conteggi dei due prefissi più corti di una e due cifre, quindi due variabili sostituiscono l’intera tabella. A ogni passaggio, il nuovo conteggio viene calcolato a partire da questi e poi entrambi avanzano di una posizione.

Python

def numDecodings(s):
    # Scrivi il codice qui

Casi di test

Caso 1

Caso 2

Caso 3

Input

s = "2611"

Atteso

Decode Ways

Funzione

Vincoli

Esempi

Suggerimenti

Soluzione

Prova entrambe le interpretazioni con la ricorsione

Ricorsione con memo

Dal basso verso l’alto con due contatori

Trappole e casi limite

Domande frequenti4

Problemi simili