Méditations LeetCode : méthodes de décodage

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 la cartographie suivante :

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

Cependant, en décodant le 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 de 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 <= longueur s <= 100
• 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 la 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 une façon de "décoder" : ne pas décoder du tout.

Ainsi, nous pouvons initialiser toutes les valeurs à 0, sauf le 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 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 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;
Copier après la connexion

Nous pouvons maintenant commencer à itérer à partir du troisième index. Nous examinerons à la fois 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 <= s.length; i++) {
  const prevDigit = s[i - 1];
  const twoPrevDigits = s.slice(i - 2, i);
  if (+prevDigit !== 0) {
    dp[i] += dp[i - 1];
  }

  if (10 <= +twoPrevDigits && +twoPrevDigits <= 26) {
    dp[i] += dp[i - 2];
  }
}

At this point, we have the result in the last index (which corresponds to s.length) so we can just return it:

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

  return dp[s.length]; 
}

Overall, this is how our solution looks like:

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 <= s.length; i++) {
    const prevDigit = s[i - 1];
    const twoPrevDigits = s.slice(i - 2, i);
    if (+prevDigit !== 0) {
      dp[i] += dp[i - 1];
    }

    if (10 <= +twoPrevDigits && +twoPrevDigits <= 26) {
      dp[i] += dp[i - 2];
    }
  }

  return dp[s.length];
}

Time and space complexity

Both the time and space complexity for this solution are $O(n)$O(n) as we iterate through all the characters doing a constant operation, and we have to keep an array whose size will grow as our input size increases.

Next up is the problem called Coin Change. Until then, happy coding.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!