Decode Ways

Q: Come si gestiscono gli zeri in Decode Ways?

Uno 0 non è mai una lettera da solo, quindi deve essere abbinato alla cifra che lo precede, come in 10 o 20 . Aggiunge il conteggio di due cifre prima solo dopo un 1 o un 2, e in caso contrario non aggiunge nulla. Uno 0 iniziale, due zeri consecutivi o uno 0 dopo un numero da 3 a 9 dà 0.

MedioProgrammazione dinamica

+10

Un messaggio composto da lettere maiuscole è stato codificato con A = 1, B = 2 e così via fino a Z = 26, e i codici sono stati scritti senza separatori. Data la stringa di cifre s, restituisci il numero di messaggi che potrebbero averla generata.

Una lettera si legge da una cifra oppure da due cifre adiacenti, e un codice non inizia mai con 0: 06 non è 6 e uno 0 isolato non è una lettera. Se nessuna lettura è valida, 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 associato al 2 che lo precede come 20, il che forza 1 20 3 (ATC). Leggere 12 per primo 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.

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), modulo 10^9+7?

Suggerimenti

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

0 di 3 aperti

Soluzione

Ogni cifra è una lettera da sola oppure si unisce a quella vicina, quindi le letture crescono come i numeri di Fibonacci: 45 cifre 1 hanno 1836311903 possibili letture. Elencarle è impossibile, ma i modi per completare una lettura dipendono solo dalla posizione raggiunta, quindi ogni posizione va conteggiata una sola volta. Uno 0 può concludere solo 10 o 20.

Prova entrambe le letture con la ricorsione

Corretto, ma non termina sui test più grandi

Intuizione

All'indice i, uno 0 non avvia alcuna lettera, quindi il percorso non produce alcuna lettura. Altrimenti leggi una cifra e conta il resto a partire da i+1; se le due cifre formano un numero da 10 a 26, leggile entrambe e conta anche a partire da i+2. Le due scelte producono lettere iniziali diverse, quindi i loro conteggi si sommano senza sovrapporsi, e arrivare alla fine completa una lettura.

Non viene memorizzato nulla, quindi le chiamate seguono la regola di Fibonacci: 45 cifre 1 richiedono circa 5 × 10^9 chiamate. Una risposta di 0 non è più veloce: 44 cifre 1, 55 cifre 3 e uno 0 finale richiedono circa 10^11 chiamate, perché ogni lettura delle cifre 1 termina solo all'ultima cifra.

Algoritmo

waysFrom(i) conta le letture delle cifre a partire dall'indice i.
Alla fine della stringa, restituisci 1. Con uno 0, restituisci 0.
Altrimenti, restituisci waysFrom(i+1), più waysFrom(i+2) quando le cifre i e i+1 formano un numero al massimo pari a 26.
La risposta è 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 una memoria

Intuizione

La ricorsione pone la stessa domanda molte volte. In "11111" serve il conteggio dall’indice 3 dopo 1 1 1, dopo 11 1 e dopo 1 11, ed è lo stesso ogni volta, perché dipende solo dalle cifre dall’indice 3 in poi. Memorizza ogni conteggio la prima volta che lo calcoli e contrassegna con -1 gli slot non ancora calcolati, poiché 0 è un conteggio reale.

Ci sono n posizioni, ciascuna calcolata una sola volta con un lavoro costante: tempo O(n). La memo e lo stack delle chiamate occupano spazio O(n), con una profondità massima di 100 chiamate.

Algoritmo

Riempi memo con -1, uno slot per indice.
In waysFrom(i), restituisci 1 alla fine della stringa e memo[i] quando non è -1.
Altrimenti conta come nella ricorsione semplice, salva il conteggio in memo[i], anche se è zero, e restituiscilo.

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

Conta invece i prefissi. Sia ways(i) il numero di decodifiche delle prime i cifre. L’ultima lettera è la cifra i-1 da sola, che deve essere compresa tra 1 e 9 e lascia ways(i-1) decodifiche, oppure le cifre i-2 e i-1 insieme, che devono formare un numero da 10 a 26 e lasciare ways(i-2). Somma le parti per cui la condizione è soddisfatta. Il prefisso vuoto ha una decodifica, quindi ways(0) = 1.

Per "1203" i conteggi sono 1, 2, poi tornano a 1 allo 0, perché funziona solo 20, che lascia il conteggio precedente al 2. Il 3 resta da solo, quindi il conteggio rimane 1. Ogni conteggio guarda due posizioni indietro, quindi due variabili sostituiscono la tabella: tempo O(n), spazio O(1).

Algoritmo

Imposta twoBack = 0 e oneBack = 1, il conteggio per il prefisso vuoto.
Per ogni indice i, imposta current su oneBack se la cifra i non è 0, altrimenti su 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 scorrere: twoBack = oneBack, poi oneBack = current.
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

Considerare 0 una lettera, oppure 06 come 6. "30", "100" e "06" hanno tutti 0 interpretazioni.
Verificare un gruppo di due cifre solo con ≤ 26. 05 è 5 come numero, ma non è un codice, quindi controlla che la prima cifra non sia 0.
Contrassegnare con 0 gli slot della memoizzazione sconosciuti. Le posizioni con 0 interpretazioni non vengono quindi mai conteggiate come memorizzate: con 44 uno, 55 tre e un 0 finale, 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.
Trasformare s in un unico numero. Cento cifre non entrano in nessun tipo intero e si perdono gli zeri iniziali che modificano la risposta.

Domande frequenti3

Qual è la complessità temporale di Decode Ways?

La soluzione bottom-up legge ogni cifra una sola volta con un lavoro costante: tempo O(n) e spazio aggiuntivo O(1). Anche la ricorsione con memoizzazione richiede tempo O(n), ma usa spazio O(n). La ricorsione semplice ha complessità 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 1 e 2. In Climbing Stairs è consentito ogni passo, quindi i conteggi sono numeri di Fibonacci. In Decode Ways un passo di una cifra richiede un numero da 1 a 9 e un passo di due cifre richiede un numero da 10 a 26, quindi ogni termine viene aggiunto solo quando la sua condizione è soddisfatta.

Come si gestiscono gli zeri in Decode Ways?

Uno 0 non è mai una lettera da solo, quindi deve essere abbinato alla cifra che lo precede, come in 10 o 20. Aggiunge il conteggio di due cifre prima solo dopo un 1 o un 2, e in caso contrario non aggiunge nulla. Uno 0 iniziale, due zeri consecutivi o uno 0 dopo un numero da 3 a 9 dà 0.

def numDecodings(s):
    # Scrivi il codice qui

Test #1

Test #2

Test #3

Argomento

s = "2611"

Output atteso

Decode Ways

Funzione

Vincoli

Esempi

Suggerimenti

Soluzione

Prova entrambe le letture con la ricorsione

Ricorsione con una memoria

Dal basso verso l’alto con due contatori

Trappole e casi limite

Domande frequenti3

Problemi simili