Vamos começar com a descrição deste problema:

Você interceptou uma mensagem secreta codificada como uma sequência de números. A mensagem é decodificada através do seguinte mapeamento:

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

No entanto, ao decodificar a mensagem, você percebe que existem muitas maneiras diferentes de decodificar a mensagem porque alguns códigos estão contidos em outros códigos ("2" e "5" vs "25").

Por exemplo, "11106" pode ser decodificado em:

• "AAJF" com o agrupamento (1, 1, 10, 6)
• "KJF" com o agrupamento (11, 10, 6)
• O agrupamento (1, 11, 06) é inválido porque "06" não é um código válido (apenas "6" é válido).

Nota: pode haver strings impossíveis de decodificar.

Dada uma string s contendo apenas dígitos, retorne o número de maneiras para decodificá-la. Se a string inteira não puder ser decodificada de forma válida, retorne 0.

Os casos de teste são gerados para que a resposta caiba em um número inteiro de 32 bits.

Por exemplo:

Input: s = "12"

Output: 2

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

Ou:

Input: s = "226"

Output: 3

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

Ou:

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.

As restrições são:

• 1
• s contém apenas dígitos e pode conter zero(s) à esquerda.

Acho que esse é um daqueles problemas que você acha que não é tão difícil à primeira vista até tentar resolvê-lo.

Primeiro, vamos começar com o insight mais simples: um caractere pode ser decodificado como ele mesmo (como apenas um caractere) ou como parte de um número de dois dígitos.
Se for a primeira opção, só podemos ter dígitos de 1 a 9, pois 0 por si só não é mapeado para nada.
No entanto, um número de dois dígitos pode ser de 10 a 26.

Como nos problemas anteriores deste capítulo, podemos começar criando um array dp para conter o número de maneiras de decodificar cada caractere à medida que iteramos pela string.
Muito semelhante ao Climbing Stairs, temos que inicializar nosso array com o comprimento s.length 1, pois precisamos considerar o fato de que ainda não decodificamos nada.
Em outras palavras, quando não há caracteres, há apenas uma maneira de "decodificar": não decodificar nada.

Então, podemos inicializar todos os valores como 0s, exceto o primeiro índice que será 1.

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

dp[0] = 1;

Novamente, semelhante aos problemas anteriores, temos que manter os dois valores inferiores, então temos que inicializar o segundo slot do nosso array que corresponde ao número de maneiras de decodificar o primeiro caractere da string.

Sabemos que não podemos decodificá-lo se for '0', então o número de maneiras de decodificá-lo será 0 neste caso.
Observe que não ser capaz de decodificar é diferente de não fazer nenhuma decodificação: no primeiro caso, o número de maneiras de decodificar é 0, mas no segundo caso (como acabamos de fazer com dp[0]), pode-se dizer que o número de maneiras de decodificar é 1.

Em todos os outros casos, há apenas uma maneira de decodificá-lo porque é apenas um único caractere. Então, inicializaremos dp[1] adequadamente:

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

Agora podemos começar a iterar a partir do terceiro índice. Veremos o dígito anterior e os dois dígitos anteriores ao mesmo tempo.

Desde que o dígito anterior não seja o número 0, podemos adicionar o que estiver no slot anterior do nosso array.

E, desde que os dois dígitos anteriores constituam um número entre 10 e 26, também podemos adicionar a solução correspondente. Resumindo, pode ser assim:

for (let i = 2; i 



Observação
Estamos convertendo os caracteres da string em números com o prático operador unário mais. Sabemos pelas restrições do problema que a string s contém apenas dígitos.


Neste ponto, temos o resultado no último índice (que corresponde a s.length) então podemos simplesmente retorná-lo:


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

  return dp[s.length]; 
}




No geral, nossa solução é assim:


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 




  
  
  Complexidade de tempo e espaço


Tanto a complexidade de tempo quanto de espaço para esta solução são $O(n)$Sobre)

 à medida que iteramos por todos os caracteres fazendo uma operação constante, temos que manter um array cujo tamanho aumentará à medida que nosso tamanho de entrada aumentar.


O próximo passo é o problema chamado Coin Change. Até então, boa codificação.