Comencemos con la descripción de este problema:

Has interceptado un mensaje secreto codificado como una cadena de números. El mensaje se decodifica mediante el siguiente mapeo:

"1" -> 'A' "2" -> 'B' ... "25" -> 'Y' "26" -> 'Z'

Sin embargo, mientras decodificas el mensaje, te das cuenta de que hay muchas maneras diferentes de decodificar el mensaje porque algunos códigos están contenidos en otros códigos ("2" y "5" frente a "25").

Por ejemplo, "11106" se puede decodificar en:

• "AAJF" con la agrupación (1, 1, 10, 6)
• "KJF" con la agrupación (11, 10, 6)
• La agrupación (1, 11, 06) no es válida porque "06" no es un código válido (solo "6" es válido).

Nota: puede haber cadenas que sean imposibles de decodificar.

Dada una cadena s que contiene solo dígitos, devuelve el número de formas para decodificarla. Si la cadena completa no se puede decodificar de ninguna manera válida, devuelve 0.

Los casos de prueba se generan para que la respuesta quepa en un entero de 32 bits.

Por ejemplo:

Input: s = "12"

Output: 2

Explanation: "12" could be decoded as "AB" (1 2) or "L" (12).

O:

Input: s = "226"

Output: 3

Explanation: "226" could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).

O:

Input: s = "06"

Output: 0

Explanation: "06" cannot be mapped to "F" because of the leading zero ("6" is different from "06"). In this case, the string is not a valid encoding, so return 0.

Las restricciones son:

• 1
• s contiene solo dígitos y puede contener ceros a la izquierda.

Creo que este es uno de esos problemas que crees que no es tan difícil a primera vista hasta que intentas resolverlo.

Primero, comencemos con la idea más simple: un carácter se puede decodificar como sí mismo (como un solo carácter) o como parte de un número de dos dígitos.
Si es la primera opción, solo podemos tener dígitos del 1 al 9, ya que el 0 por sí solo no está asignado a nada.
Sin embargo, un número de dos dígitos puede ser del 10 al 26.

Al igual que con los problemas anteriores de este capítulo, podemos comenzar creando una matriz dp para contener la cantidad de formas de decodificar hasta cada carácter a medida que iteramos a través de la cadena.
Muy similar a Subir escaleras, tenemos que inicializar nuestra matriz con la longitud s.length 1 ya que debemos considerar el hecho de que aún no hemos decodificado nada.
En otras palabras, cuando no hay caracteres, sólo hay una forma de "decodificar": no decodificar en absoluto.

Entonces, podemos inicializar todos los valores como 0, excepto el primer índice que será 1.

let dp = Array.from({ length: s.length   1 }, () => 0);

dp[0] = 1;

Nuevamente, similar a los problemas anteriores, tenemos que mantener los dos valores inferiores, por lo que tenemos que inicializar la segunda ranura de nuestra matriz que corresponde al número de formas de decodificar el primer carácter de la cadena.

Sabemos que no podemos decodificarlo si es '0', por lo que el número de formas de decodificarlo será 0 en este caso.
Tenga en cuenta que no poder decodificar es diferente de no realizar ninguna decodificación: en el primer caso, el número de formas de decodificar es 0, pero en el segundo caso (como acabamos de hacer con dp[0]), se puede decir que el número de formas de decodificar es 1.

En todos los demás casos, solo hay una forma de decodificarlo porque es solo un carácter. Entonces, inicializaremos dp[1] en consecuencia:

dp[1] = (s[0] === '0') ? 0 : 1;

Ahora podemos comenzar a iterar desde el tercer índice. Veremos tanto el dígito anterior como los dos dígitos anteriores al mismo tiempo.

Siempre que el dígito anterior no sea el número 0, podemos agregar lo que esté en la ranura anterior de nuestra matriz.

Y, siempre que los dos dígitos anteriores constituyan un número entre 10 y 26, también podemos sumar la solución correspondiente. En definitiva, puede verse así:

for (let i = 2; i 






Nota




Estamos convirtiendo los caracteres de cadena en números con el práctico operador unario más. Sabemos por las restricciones del problema que la cadena s solo contiene dígitos.




En este punto, tenemos el resultado en el último índice (que corresponde a s.length) así que podemos devolverlo:



function numDecodings(s: string): number {
  /* ... */

  return dp[s.length]; 
}




En general, así es como se ve nuestra solución:



function numDecodings(s: string): number {
  let dp = Array.from({ length: s.length   1 }, () => 0);

  dp[0] = 1;
  dp[1] = (s[0] === '0') ? 0 : 1;

  for (let i = 2; i 




  
  
  Complejidad temporal y espacial


La complejidad temporal y espacial de esta solución es 


  $O(n)$En)

 a medida que iteramos a través de todos los caracteres haciendo una operación constante, y tenemos que mantener una matriz cuyo tamaño crecerá a medida que aumente nuestro tamaño de entrada.




El siguiente es el problema llamado Cambio de moneda. Hasta entonces, feliz codificación.