Decode Ways

Q: Comment gérer les zéros dans Decode Ways ?

Un 0 ne peut jamais être une lettre à lui seul : il doit donc être associé au chiffre qui le précède, et seuls 10 et 20 sont des codes. Dans la boucle ascendante, cela signifie qu’un 0 n’ajoute rien pour le cas à un chiffre et n’ajoute le nombre de possibilités obtenu deux chiffres plus tôt qu’après un 1 ou un 2. Un 0 en tête, deux zéros consécutifs ou un 0 après un chiffre de 3 à 9 donnent une réponse de 0.

MoyenProgrammation dynamique

+10

Un message composé de lettres majuscules a été converti en chiffres à l’aide du code A = 1, B = 2, et ainsi de suite jusqu’à Z = 26, puis les codes ont été écrits les uns à la suite des autres sans séparateurs. Vous obtenez la chaîne de chiffres s. Retournez le nombre de messages différents qui auraient pu la produire.

Chaque lettre est lue à partir d’un chiffre ou de deux chiffres côte à côte, et un code ne commence jamais par 0 : 06 ne vaut pas 6, et un 0 seul ne correspond à aucune lettre. Si aucune lecture ne fonctionne, retournez 0.

Fonction

numDecodings(s: string) → integer

sstring: la chaîne de chiffres à décoder
Renvoieinteger: le nombre de messages de lettres qui s’encodent en s

Contraintes

1 ≤ s.length ≤ 100
s contient uniquement les chiffres 0 à 9, et peut commencer par 0.
Tous les préfixes et tous les suffixes de s ont moins de 2³¹ lectures, donc la réponse et tous les nombres que tu calcules en cours de route tiennent dans un entier signé de 32 bits.

Exemples

Entrée: s = "2611"
Sortie: 4
Explication: Les quatre lectures sont 2 6 1 1 (BFAA), 26 1 1 (ZAA), 2 6 11 (BFK) et 26 11 (ZK). Les chiffres du milieu ne s’associent jamais, car 61 est supérieur à 26.

Entrée: s = "1203"
Sortie: 1
Explication: Le 0 doit être associé au 2 qui le précède pour former 20, ce qui impose la lecture 1 20 3 (ATC). Lire 12 en premier laisserait le 0 seul, et 03 commence par 0.

Entrée: s = "06"
Sortie: 0
Explication: La première lettre devrait commencer par 0. Un 0 isolé n’est pas une lettre et 06 n’est pas un code, donc aucun message ne donne cette chaîne.

+25 tests cachés à la soumission

Pour aller plus loin

Et si s pouvait également contenir *, qui représente n’importe quel chiffre de 1 à 9 ? Peux-tu compter les lectures en temps O(n), en renvoyant le nombre modulo 10^9+7 ?

Indices

Ouvrez-les un par un. Chacun en dévoile un peu plus.

0 sur 3 ouverts

Solution

Chaque chiffre est soit une lettre à lui seul, soit s’associe à son voisin pour former une lettre à deux chiffres ; le nombre de lectures croît donc comme les nombres de Fibonacci : 45 chiffres 1 donnent déjà 1836311903 lectures. Les énumérer est impossible. La clé du problème, c’est que le nombre de façons de terminer une lecture dépend uniquement de la position atteinte : il suffit donc de compter une fois chaque position. C’est avec les zéros qu’il faut être vigilant : un 0 ne peut être que le deuxième chiffre de 10 ou de 20.

Essayez les deux lectures avec la récursivité

Correcte, mais ne termine pas sur les plus gros tests

Intuition

Place-toi à l’indice i et regarde le chiffre suivant. S’il s’agit de 0, aucune lettre ne commence ici et ce chemin ne donne aucun décodage. Sinon, tu peux lire ce chiffre comme une lettre et compter les décodages du reste à partir de i+1. S’il forme un nombre compris entre 10 et 26 avec le chiffre qui le suit, tu peux aussi lire les deux chiffres comme une seule lettre et compter à partir de i+2. Les deux choix donnent des premières lettres différentes, donc leurs nombres s’additionnent sans chevauchement. Lorsque i atteint la fin de la chaîne, tu as terminé un décodage complet, donc tu renvoies 1.

Avec "2611" : la première lettre est 2 ou 26. Après 2, la lettre suivante doit être 6, car 61 est trop grand. Les deux branches se terminent ensuite par 1 1 ou 11, donc le total est de 2 × 2 = 4.

La réponse est correcte, mais rien n’est mémorisé. Pour une chaîne composée uniquement de 1, chaque appel se divise en deux et les appels suivent la règle de Fibonacci : 45 uns nécessitent donc environ 5 × 10^9 appels. Le travail ne diminue pas non plus avec la réponse : avec 44 uns suivis de 55 trois et d’un 0 final, la réponse est 0, mais la récursion parcourt tous les décodages des uns à travers tous les trois avant que chaque chemin n’échoue au dernier chiffre, soit environ 10^11 appels.

Algorithme

Écrivez une fonction auxiliaire waysFrom(i) qui compte les lectures des chiffres depuis l’index i jusqu’à la fin.
Si i est égal à la longueur de s, renvoyez 1.
Si le chiffre à l’index i est 0, renvoyez 0.
Commencez par waysFrom(i+1), les lectures dont la lettre suivante correspond à un seul chiffre.
Si les chiffres aux index i et i+1 forment un nombre inférieur ou égal à 26, ajoutez waysFrom(i+2). Renvoyez 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)

Récursion avec mémoïsation

Intuition

La récursion pose la même question encore et encore. Dans "11111", le décompte à partir de l’index 3 est nécessaire après 1 1 1, après 11 1 et après 1 11, et il est identique à chaque fois, car il dépend uniquement des chiffres à partir de l’index 3. Enregistre chaque décompte dans un tableau memo la première fois que tu le calcules, puis récupère-le là par la suite.

Marque les cases qui n’ont pas encore été calculées avec -1, et non avec 0. Zéro est une vraie réponse ici : dans une chaîne qui se termine par 30, chaque position a 0 lecture. Avec 0 comme marqueur, ces positions semblent inconnues à chaque visite et la récursion est aussi lente qu’avant.

Il y a n positions, et chacune est calculée une seule fois en un temps constant, donc le temps d’exécution est O(n). Le mémo et la pile d’appels prennent chacun O(n) d’espace. Les appels s’imbriquent ici sur au plus 100 niveaux, ce que tous les langages gèrent.

Algorithme

Crée un tableau memo avec un emplacement par index, tous initialisés à -1.
Dans waysFrom(i), renvoie 1 à la fin de la chaîne et memo[i] lorsqu’il n’est pas égal à -1.
Sinon, compte comme dans la récursion simple : 0 pour un 0, sinon waysFrom(i+1) plus waysFrom(i+2) lorsque les deux chiffres forment un nombre de 10 à 26.
Enregistre le nombre dans memo[i], même s’il vaut zéro, puis renvoie-le.
Renvoie 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 bas en haut avec deux compteurs

Intuition

Inversez la récurrence et comptez les préfixes. Soit ways(i) le nombre de lectures des i premiers chiffres. La dernière lettre d’une telle lecture est soit le chiffre à l’index i-1 seul, ce qui nécessite un chiffre de 1 à 9 et laisse ways(i-1) lectures pour le reste, soit les deux chiffres aux index i-2 et i-1, qui doivent former un nombre de 10 à 26 et laissent ways(i-2). Ainsi, ways(i) est la somme des parties dont la condition est satisfaite. Le préfixe vide a une lecture, le message vide, donc ways(0) = 1.

Parcourons "1203". Après 1, le compte est de 1. Après 12, il est de 2 : 1 2 et 12. Le 0 ne peut pas être seul et seul 20 fonctionne, donc le compte revient à celui d’avant le 2, qui est 1. Le 3 peut être seul et 03 n’est pas un code, donc le compte reste à 1.

Chaque compte ne dépend que des deux comptes précédents, donc deux variables, twoBack et oneBack, remplacent le tableau. Cela fait un seul parcours avec un travail constant par chiffre : temps en O(n), espace en O(1) et aucune récursion.

Algorithme

Définissez twoBack = 0 et oneBack = 1, le nombre de façons de décoder le préfixe vide.
Pour chaque indice i, initialisez current à 0, puis ajoutez oneBack si le chiffre i n’est pas 0.
Si i ≥ 1, que le chiffre i-1 n’est pas 0 et que les chiffres i-1 et i forment un nombre inférieur ou égal à 26, ajoutez twoBack.
Décalez les valeurs : twoBack = oneBack, puis oneBack = current.
Après le dernier chiffre, renvoyez 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

Pièges et cas limites

Presque toutes les mauvaises réponses à ce problème sont dues aux zéros ou à une mémoïsation qui oublie.

Traiter 0 comme une lettre, ou 06 comme 6. Un zéro ne peut terminer que 10 ou 20, donc "30", "100" et "06" ont tous 0 décodage.
Tester uniquement si un bloc de deux chiffres est inférieur ou égal à 26. 05 vaut 5 comme nombre, mais ce n’est pas un code. Vérifie que le premier des deux chiffres n’est pas 0.
Utiliser 0 comme marqueur pour une case de mémo qui n’a pas encore été calculée. De nombreuses positions ont réellement 0 décodage, donc ces cases ne sont jamais considérées comme enregistrées et sont recalculées à chaque visite. Avec 44 uns suivis de trois et d’un 0 final, toutes les cases valent 0 et tu retombes sur environ 10^11 appels.
Lire le chiffre avant l’indice 0. Protège le test des deux chiffres avec i ≥ 1 : en Python, s[-1] lit silencieusement le dernier chiffre, et dans d’autres langages, on lit en dehors de la chaîne.
Convertir s en un seul nombre. Cent chiffres ne tiennent dans aucun type entier, et la conversion supprime les zéros initiaux, ce qui modifie la réponse. Traite les chiffres un par un.
En Lua et en R, les positions commencent à 1, donc la fin de la chaîne est à la position n+1 et le premier test de deux chiffres se fait à la position 2.

Questions fréquentes4

Quelle est la complexité temporelle de Decode Ways ?

La solution ascendante lit chaque chiffre une seule fois avec un travail constant ; elle s’exécute donc en temps O(n) et utilise un espace supplémentaire O(1). La récursion avec mémoïsation s’exécute également en temps O(n), mais utilise un espace O(n) pour la mémoïsation et la pile d’appels. La récursion simple est exponentielle : sur une chaîne composée de 1, le nombre d’appels augmente comme 1.618^n.

Quel est le lien entre Decode Ways et Climbing Stairs ?

Les deux comptent les façons de parcourir une ligne avec des pas de taille 1 et 2. Dans Climbing Stairs, chaque pas est autorisé, donc le nombre de façons est un nombre de Fibonacci. Dans Decode Ways, un pas d’un chiffre nécessite un chiffre de 1 à 9 et un pas de deux chiffres nécessite un nombre de 10 à 26 ; chaque terme de la somme n’est donc ajouté que lorsque sa condition est remplie. Une chaîne composée uniquement de 1 permet tous les pas, et ses nombres de façons sont exactement les nombres de Fibonacci.

Comment gérer les zéros dans Decode Ways ?

Un 0 ne peut jamais être une lettre à lui seul : il doit donc être associé au chiffre qui le précède, et seuls 10 et 20 sont des codes. Dans la boucle ascendante, cela signifie qu’un 0 n’ajoute rien pour le cas à un chiffre et n’ajoute le nombre de possibilités obtenu deux chiffres plus tôt qu’après un 1 ou un 2. Un 0 en tête, deux zéros consécutifs ou un 0 après un chiffre de 3 à 9 donnent une réponse de 0.

Peut-on résoudre Decode Ways avec un espace O(1) ?

Oui. Le nombre pour un préfixe dépend uniquement des nombres pour les deux préfixes de respectivement un et deux chiffres de moins, donc deux variables remplacent le tableau entier. À chaque étape, le nouveau nombre est calculé à partir de ces deux nombres, qui sont ensuite décalés d’une position.

Python

def numDecodings(s):
    # Écrivez le code ici

Cas de test

Cas 1

Cas 2

Cas 3

Entrée

s = "2611"

Attendu

Decode Ways

Fonction

Contraintes

Exemples

Indices

Solution

Essayez les deux lectures avec la récursivité

Récursion avec mémoïsation

De bas en haut avec deux compteurs

Pièges et cas limites

Questions fréquentes4

Problèmes similaires