Decode Ways

Q: ¿Cómo se manejan los ceros en Decode Ways?

Un 0 nunca es una letra por sí solo, así que debe ir junto con el dígito anterior, como 10 o 20 . Suma el conteo de dos dígitos atrás solo después de un 1 o un 2, y nada en los demás casos. Un 0 inicial, dos ceros seguidos o un 0 después de 3 a 9 da 0.

MedioProgramación dinámica

+10

Un mensaje de letras mayúsculas se codificó con A = 1, B = 2 y así sucesivamente hasta Z = 26, y los códigos se escribieron sin separadores. Dada la cadena de dígitos s, devuelve cuántos mensajes podrían haberla producido.

Una letra se lee a partir de uno o dos dígitos adyacentes, y un código nunca empieza por 0: 06 no es 6, y un 0 aislado no es una letra. Si ninguna lectura funciona, devuelve 0.

Función

numDecodings(s: string) → integer

sstring: la cadena de dígitos que se va a decodificar
Devuelveinteger: el número de mensajes de letras que se codifican en s

Restricciones

1 ≤ s.length ≤ 100
s contiene solo los dígitos 0 a 9, y puede empezar con 0.
Cada prefijo y cada sufijo de s tiene menos de 2³¹ lecturas, así que la respuesta y cada recuento que calcules por el camino caben en un entero de 32 bits con signo.

Ejemplos

Entrada: s = "2611"
Salida: 4
Explicación: Las cuatro lecturas son 2 6 1 1 (BFAA), 26 1 1 (ZAA), 2 6 11 (BFK) y 26 11 (ZK). Los dígitos del medio nunca se emparejan, porque 61 es mayor que 26.

Entrada: s = "1203"
Salida: 1
Explicación: El 0 debe emparejarse con el 2 que está antes, formando 20, lo que fuerza 1 20 3 (ATC). Leer primero 12 dejaría el 0 solo, y 03 empieza con 0.

Entrada: s = "06"
Salida: 0
Explicación: La primera letra tendría que empezar con 0. Un 0 aislado no es una letra y 06 no es un código, así que ningún mensaje produce esta cadena.

Para ir más allá

¿Qué pasa si s también puede contener *, que representa cualquier dígito del 1 al 9? ¿Puedes contar las lecturas en tiempo O(n), módulo 10^9+7?

Pistas

Ábrelas de una en una. Cada una revela un poco más.

0 de 3 abiertas

Solución

Cada dígito es una letra por sí solo o se une a su vecino, así que las cantidades de interpretaciones crecen como los números de Fibonacci: 45 unos tienen 1836311903 interpretaciones. Enumerarlas es imposible, pero las formas de completar una interpretación dependen solo de la posición alcanzada, así que cada posición debe contarse una vez. Un 0 solo puede terminar 10 o 20.

Prueba ambas lecturas con recursión

Correcto, pero no termina con las pruebas más grandes

Intuición

En el índice i, un 0 no inicia ninguna letra, así que la ruta no genera ninguna lectura. De lo contrario, lee un dígito y cuenta el resto a partir de i+1; si los dos dígitos forman un número del 10 al 26, lee también ambos y cuenta a partir de i+2. Las dos opciones dan letras iniciales distintas, así que sus recuentos se suman sin solaparse, y llegar al final completa una lectura.

No se recuerda nada, así que las llamadas siguen la regla de Fibonacci: 45 unos requieren alrededor de 5 × 10^9 llamadas. Una respuesta de 0 no es más rápida: 44 unos, 55 dígitos 3 y un 0 final requieren alrededor de 10^11 llamadas, ya que cada lectura de los unos solo llega a un callejón sin salida en el último dígito.

Algoritmo

waysFrom(i) cuenta las lecturas de los dígitos desde el índice i en adelante.
Al final de la cadena, devuelve 1. Si hay un 0, devuelve 0.
De lo contrario, devuelve waysFrom(i+1), más waysFrom(i+2) cuando los dígitos i y i+1 forman un número de como máximo 26.
La respuesta es 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)

Recursión con una memoria

Intuición

La recursión plantea la misma pregunta muchas veces. En "11111", se necesita el conteo desde el índice 3 después de 1 1 1, después de 11 1 y después de 1 11, y es el mismo cada vez, porque depende únicamente de los dígitos a partir del índice 3. Guarda cada conteo la primera vez que lo calculas y marca las posiciones aún no calculadas con -1, ya que 0 es un conteo real.

Hay n posiciones, cada una se calcula una sola vez con trabajo constante: tiempo O(n). La memoria memo y la pila de llamadas ocupan espacio O(n), con una profundidad máxima de 100 llamadas.

Algoritmo

Rellena memo con -1, un espacio por índice.
En waysFrom(i), devuelve 1 al final de la cadena y memo[i] cuando no sea -1.
De lo contrario, cuenta como en la recursión simple, guarda el recuento en memo[i], incluido el cero, y devuélvelo.

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)

De abajo arriba con dos contadores

Intuición

En cambio, cuenta los prefijos. Sea ways(i) el número de lecturas de los primeros i dígitos. La última letra es o bien el dígito i-1 por sí solo, que debe estar entre 1 y 9 y deja ways(i-1) lecturas, o bien los dígitos i-2 y i-1 juntos, que deben formar un número entre 10 y 26 y dejan ways(i-2). Suma las partes cuya condición se cumple. El prefijo vacío tiene una lectura, así que ways(0) = 1.

Con "1203", los recuentos van 1, 2 y después vuelven a 1 en el 0, porque solo sirve 20 y deja el recuento que había antes del 2. El 3 va por sí solo, así que el recuento permanece en 1. Cada recuento mira dos posiciones atrás, así que dos variables reemplazan la tabla: tiempo O(n), espacio O(1).

Algoritmo

Establece twoBack = 0 y oneBack = 1, el recuento para el prefijo vacío.
Para cada índice i, establece current en oneBack si el dígito i no es 0; de lo contrario, en 0.
Si i ≥ 1, el dígito i-1 no es 0 y los dígitos i-1 y i forman un número de como máximo 26, suma twoBack.
Desplaza: twoBack = oneBack, después oneBack = current.
Devuelve 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

Errores comunes y casos límite

Tratar 0 como una letra, o 06 como 6. "30", "100" y "06" tienen 0 lecturas.
Probar una secuencia de dos dígitos solo con ≤ 26. 05 es 5 como número, pero no como código, así que comprueba que su primer dígito no sea 0.
Marcar las posiciones desconocidas de la memoria caché con 0. Las posiciones con 0 lecturas nunca cuentan como almacenadas: con 44 unos, 55 treses y un 0 final, vuelves a unas 10^11 llamadas.
Leer el dígito anterior al índice 0. Protege la comprobación de dos dígitos con i ≥ 1; en Python, s[-1] lee silenciosamente el último dígito.
Convertir s en un solo número. Cien dígitos no caben en ningún tipo entero, y se pierden los ceros iniciales que cambian la respuesta.

Preguntas frecuentes3

¿Cuál es la complejidad temporal de Decode Ways?

La solución ascendente lee cada dígito una vez con trabajo constante: tiempo O(n) y espacio adicional O(1). La recursión con memorización también requiere tiempo O(n), pero usa espacio O(n). La recursión simple es exponencial: con una cadena de unos, el número de llamadas crece como 1.618^n.

¿Qué relación tiene Decode Ways con Climbing Stairs?

Ambos cuentan las formas de cubrir una línea con pasos de 1 y 2. En Climbing Stairs se permite cada paso, así que los recuentos son números de Fibonacci. En Decode Ways, un paso de un dígito necesita un valor del 1 al 9 y un paso de dos dígitos necesita un valor del 10 al 26, así que cada término se suma solo cuando se cumple su condición.

¿Cómo se manejan los ceros en Decode Ways?

Un 0 nunca es una letra por sí solo, así que debe ir junto con el dígito anterior, como 10 o 20. Suma el conteo de dos dígitos atrás solo después de un 1 o un 2, y nada en los demás casos. Un 0 inicial, dos ceros seguidos o un 0 después de 3 a 9 da 0.

def numDecodings(s):
    # Escribe el código aquí

Prueba #1

Prueba #2

Prueba #3

Argumento

s = "2611"

Salida Esperada

Decode Ways

Función

Restricciones

Ejemplos

Pistas

Solución

Prueba ambas lecturas con recursión

Recursión con una memoria

De abajo arriba con dos contadores

Errores comunes y casos límite

Preguntas frecuentes3

Problemas similares