Commençons par la description de ce problème :

Vous avez intercepté un message secret codé sous forme de chaîne de chiffres. Le message est décodé via le mappage suivant :

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

Cependant, lors du décodage du message, vous réalisez qu'il existe de nombreuses façons différentes de décoder le message car certains codes sont contenus dans d'autres codes ("2" et "5" contre "25").

Par exemple, "11106" peut être décodé en :

• "AAJF" avec le regroupement (1, 1, 10, 6)
• "KJF" avec le groupement (11, 10, 6)
• Le regroupement (1, 11, 06) n'est pas valide car "06" n'est pas un code valide (seul "6" est valide).

Remarque : certaines chaînes peuvent être impossibles à décoder.

Étant donné une chaîne s contenant uniquement des chiffres, renvoie le nombre de façons pour la décoder. Si la chaîne entière ne peut pas être décodée de manière valide, renvoyez 0.

Les cas de test sont générés de manière à ce que la réponse tienne dans un entier 32 bits.

Par exemple:

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.

Les contraintes sont :

• 1
• s ne contient que des chiffres et peut contenir des zéros non significatifs.

Je pense que c'est l'un de ces problèmes qui, à première vue, ne semblent pas si difficiles jusqu'à ce que vous essayiez de le résoudre.

Tout d'abord, commençons par l'idée la plus simple : un caractère peut être décodé soit comme lui-même (comme un seul caractère), soit comme une partie d'un nombre à deux chiffres.
Si c'est la première option, nous ne pouvons avoir que des chiffres de 1 à 9, car 0 en lui-même n'est mappé à rien.
Cependant, un nombre à deux chiffres peut aller de 10 à 26.

Comme pour les problèmes précédents de ce chapitre, nous pouvons commencer par créer un tableau dp pour contenir le nombre de façons de décoder jusqu'à chaque caractère au fur et à mesure que nous parcourons la chaîne.
Très similaire à Climbing Stairs, nous devons initialiser notre tableau avec la longueur s.length 1 car nous devons tenir compte du fait que nous n'avons encore rien décodé.
En d'autres termes, lorsqu'il n'y a pas de caractères, il n'y a qu'une façon de "décoder" : pas de décodage du tout.

Ainsi, nous pouvons initialiser toutes les valeurs à 0, à l'exception du premier index qui sera 1.

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

dp[0] = 1;

Encore une fois, comme pour les problèmes précédents, nous devons conserver les deux valeurs du bas, nous devons donc initialiser le deuxième emplacement de notre tableau qui correspond au nombre de façons de décoder le premier caractère de la chaîne.

Nous savons que nous ne pouvons pas le décoder s'il vaut « 0 », donc le nombre de façons de le décoder sera de 0 dans ce cas.
Notez que ne pas pouvoir décoder est différent de ne pas décoder du tout : dans le premier cas, le nombre de façons de décoder est de 0, mais dans le second cas (comme nous venons de le faire avec dp[0]), on peut dire que le nombre de façons de décoder est de 1.

Dans tous les autres cas, il n'y a qu'une façon de le décoder car il ne s'agit que d'un seul caractère. Nous allons donc initialiser dp[1] en conséquence :

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

Nous pouvons maintenant commencer à itérer à partir du troisième index. Nous examinerons simultanément le chiffre précédent et les deux chiffres précédents.

Tant que le chiffre précédent n'est pas le chiffre 0, nous pouvons ajouter tout ce qui se trouve dans l'emplacement précédent de notre tableau.

Et, tant que les deux chiffres précédents constituent un nombre compris entre 10 et 26, nous pouvons également ajouter la solution correspondante. En résumé, cela peut ressembler à ceci :

for (let i = 2; i 



Note
Nous convertissons les caractères de chaîne en nombres avec l'opérateur unaire plus pratique. Nous savons, grâce aux contraintes du problème, que la chaîne s ne contient que des chiffres.


À ce stade, nous avons le résultat dans le dernier index (qui correspond à s.length) donc nous pouvons simplement le renvoyer :


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

  return dp[s.length]; 
}




Dans l'ensemble, voici à quoi ressemble notre solution :


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 




  
  
  Complexité temporelle et spatiale


La complexité temporelle et spatiale de cette solution est $O(n)$Sur)

 lorsque nous parcourons tous les caractères en effectuant une opération constante, nous devons conserver un tableau dont la taille augmentera à mesure que la taille de notre entrée augmente.


 La prochaine étape est le problème appelé Coin Change. En attendant, bon codage.