Decode Ways

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

Un 0 nunca puede ser una letra por sí solo, así que debe emparejarse con el dígito que tiene delante, y solo 10 y 20 son códigos. En el bucle ascendente, eso significa que un 0 no suma nada en el caso de un solo dígito y solo suma el recuento de dos dígitos atrás después de un 1 o un 2. Un 0 inicial, dos ceros seguidos o un 0 después de un dígito del 3 al 9 hacen que la respuesta sea 0.

MedioProgramación dinámica

+10

Un mensaje compuesto por letras mayúsculas se convirtió en dígitos mediante el código A = 1, B = 2 y así sucesivamente hasta Z = 26, y los códigos se escribieron uno tras otro sin separadores. Recibes la cadena de dígitos s. Devuelve cuántos mensajes diferentes podrían haberla producido.

Cada letra se lee a partir de uno o dos dígitos consecutivos, y un código nunca empieza con 0: 06 no es 6, y un 0 por sí solo no es una letra. Si no hay ninguna lectura posible, devuelve 0.

Función

numDecodings(s: string) → integer

sstring: la cadena de dígitos que se debe decodificar
Devuelveinteger: el número de mensajes de una letra que codifican s

Restricciones

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

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 tiene que emparejarse con el 2 que tiene delante para formar 20, lo que obliga a leer 1 20 3 (ATC). Leer primero 12 dejaría el 0 solo, y 03 empieza por 0.

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

+25 pruebas ocultas al enviar

Para ir más allá

¿Y si s también puede contener *, que representa cualquier dígito del 1 al 9? ¿Puedes contar las lecturas en tiempo O(n) y devolver el recuento 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 para formar una letra de dos dígitos, así que el número de lecturas crece como los números de Fibonacci: 45 unos ya tienen 1836311903 lecturas. Enumerarlas no tiene sentido. La clave para resolver el problema es que el número de formas de terminar una lectura depende únicamente de la posición a la que has llegado, así que cada posición debe contarse una sola vez. Hay que prestar atención a los ceros: un 0 solo puede ser el segundo dígito de 10 o 20.

Prueba ambas lecturas con recursión

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

Intuición

Colócate en el índice i y mira el siguiente dígito. Si es 0, aquí no empieza ninguna letra y este camino no produce ninguna lectura. De lo contrario, puedes leer ese dígito como una letra y contar las lecturas del resto desde i+1. Si junto con el dígito siguiente forma un número del 10 al 26, también puedes leer ambos como una sola letra y contar desde i+2. Las dos opciones dan letras iniciales diferentes, así que sus cantidades se suman sin superponerse. Cuando i llega al final de la cadena, has completado una lectura, así que devuelves 1.

Con "2611": la primera letra es 2 o 26. Después de 2, la siguiente letra debe ser 6, porque 61 es demasiado grande. Ambas ramas terminan entonces con 1 1 o 11, así que el total es 2 × 2 = 4.

La respuesta es correcta, pero no se recuerda nada. En una cadena de unos, cada llamada se ramifica en dos y las llamadas siguen la regla de Fibonacci, así que 45 unos requieren alrededor de 5 × 10^9 llamadas. El trabajo tampoco disminuye junto con la respuesta: con 44 unos seguidos de 55 treses y un 0 final, la respuesta es 0, pero la recursión recorre todas las lecturas de los unos a través de todos los treses antes de que cada camino termine en el último dígito, unas 10^11 llamadas.

Algoritmo

Escribe una función auxiliar waysFrom(i) que cuente las lecturas de los dígitos desde el índice i hasta el final.
Si i es igual a la longitud de s, devuelve 1.
Si el dígito en i es 0, devuelve 0.
Empieza con waysFrom(i+1), las lecturas cuya siguiente letra ocupa un dígito.
Si los dígitos i y i+1 forman un número de como máximo 26, suma waysFrom(i+2). Devuelve 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 memoización

Intuición

La recursión plantea la misma pregunta una y otra vez. En "11111", se necesita el recuento desde el índice 3 después de 1 1 1, después de 11 1 y después de 1 11, y el resultado es el mismo cada vez, porque depende solo de los dígitos desde el índice 3 en adelante. Guarda cada recuento en un array memo la primera vez que lo calculas y léelo de ahí después.

Marca las posiciones que aún no se han calculado con -1, no con 0. Cero es una respuesta válida aquí: en una cadena que termina en 30, todas las posiciones tienen 0 lecturas. Si usas 0 como marca, esas posiciones parecen desconocidas en cada visita y la recursión es tan lenta como antes.

Hay n posiciones y cada una se calcula una vez con un trabajo constante, así que el tiempo es O(n). El memo y la pila de llamadas ocupan cada uno un espacio de O(n). Las llamadas se anidan hasta 100 niveles aquí, algo que cualquier lenguaje puede manejar.

Algoritmo

Crea un array memo con una posición por índice, todas establecidas en -1.
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: 0 para un 0; en caso contrario, waysFrom(i+1) más waysFrom(i+2) cuando los dos dígitos formen un número del 10 al 26.
Guarda el recuento en memo[i], incluido el cero, y devuélvelo.
Devuelve 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)

De abajo arriba con dos contadores

Intuición

Invierte la recursión y cuenta los prefijos. Sea ways(i) el número de lecturas de los primeros i dígitos. La última letra de una lectura así es o bien el dígito del índice i-1 por sí solo, que debe ser un dígito del 1 al 9 y deja ways(i-1) lecturas para el resto, o bien los dos dígitos en i-2 y i-1, que deben formar un número del 10 al 26 y dejan ways(i-2). Por tanto, ways(i) es la suma de las partes cuya condición se cumple. El prefijo vacío tiene una lectura, el mensaje vacío, así que ways(0) = 1.

Recorre "1203". Después de 1, el recuento es 1. Después de 12, es 2: 1 2 y 12. El 0 no puede aparecer por sí solo y solo funciona 20, así que el recuento vuelve al que había antes del 2, que es 1. El 3 aparece por sí solo y 03 no es un código, así que el recuento se mantiene en 1.

Cada recuento solo consulta los dos recuentos anteriores, así que dos variables, twoBack y oneBack, sustituyen a la tabla. Es una sola pasada con trabajo constante por dígito: tiempo O(n), espacio O(1) y nada de recursión.

Algoritmo

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

Casi todas las respuestas incorrectas a este problema se deben a los ceros o a una memoización que olvida.

Tratar 0 como una letra, o 06 como 6. Un cero solo puede completar 10 o 20, así que "30", "100" y "06" tienen 0 lecturas.
Probar una parte de dos dígitos usando solo ≤ 26. 05 es 5 como número, pero no es un código. Comprueba que el primero de los dos dígitos no sea 0.
Usar 0 como marca para una posición de memoización que aún no se ha calculado. Muchas posiciones realmente tienen 0 lecturas, así que esas posiciones nunca se cuentan como almacenadas y se vuelven a calcular en cada visita. Con 44 unos seguidos de tres y un 0 final, todas las posiciones valen 0 y vuelves a tener 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, y otros lenguajes leen fuera de la cadena.
Convertir s en un único número. Cien dígitos no caben en ningún tipo entero, y la conversión elimina los ceros iniciales, que cambian la respuesta. Procesa los dígitos uno por uno.
En Lua y R, las posiciones empiezan en 1, así que el final de la cadena está en la posición n+1 y la primera comprobación de dos dígitos está en la posición 2.

Preguntas frecuentes4

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

La solución ascendente lee cada dígito una vez con un trabajo constante, por lo que se ejecuta en O(n) de tiempo y O(1) de espacio adicional. La recursión con memorización también requiere O(n) de tiempo, pero usa O(n) de espacio para la memoria y la pila de llamadas. La recursión simple es exponencial: en 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 tamaño 1 y 2. En Climbing Stairs se permite cada paso, así que el recuento es un número de Fibonacci. En Decode Ways, un paso de un dígito necesita un dígito del 1 al 9 y un paso de dos dígitos necesita un número del 10 al 26, así que cada término de la suma se añade solo cuando se cumple su condición. Una cadena de unos permite cada paso, y sus recuentos son exactamente los números de Fibonacci.

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

Un 0 nunca puede ser una letra por sí solo, así que debe emparejarse con el dígito que tiene delante, y solo 10 y 20 son códigos. En el bucle ascendente, eso significa que un 0 no suma nada en el caso de un solo dígito y solo suma el recuento de dos dígitos atrás después de un 1 o un 2. Un 0 inicial, dos ceros seguidos o un 0 después de un dígito del 3 al 9 hacen que la respuesta sea 0.

¿Se puede resolver Decode Ways en espacio O(1)?

Sí. El recuento de un prefijo depende únicamente de los recuentos de los dos prefijos que tienen uno y dos dígitos menos, por lo que dos variables sustituyen a toda la tabla. En cada paso, se calcula el nuevo recuento a partir de ellos y se desplazan una posición.

Python

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

Casos de prueba

Caso 1

Caso 2

Caso 3

Entrada

s = "2611"

Esperado

Decode Ways

Función

Restricciones

Ejemplos

Pistas

Solución

Prueba ambas lecturas con recursión

Recursión con una memoización

De abajo arriba con dos contadores

Errores comunes y casos límite

Preguntas frecuentes4

Problemas similares