Decode Ways

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

Un 0 n’est jamais une lettre à lui seul, il doit donc s’associer au chiffre qui le précède, comme dans 10 ou 20 . Il ajoute le décompte d’il y a deux chiffres uniquement après un 1 ou un 2, et rien dans les autres cas. Un 0 en tête, deux zéros à la suite ou un 0 après un chiffre de 3 à 9 donne 0.

MoyenProgrammation dynamique

+10

Un message composé de lettres majuscules a été encodé avec A = 1, B = 2, et ainsi de suite jusqu’à Z = 26, puis les codes ont été écrits sans séparateurs. Étant donné la chaîne de chiffres s, renvoie le nombre de messages qui auraient pu la produire.

Une lettre se lit à partir d’un chiffre ou de deux chiffres adjacents, et un code ne commence jamais par 0 : 06 ne vaut pas 6, et un 0 isolé ne correspond à aucune lettre. Si aucune lecture ne fonctionne, renvoie 0.

Fonction

numDecodings(s: string) → integer

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

Contraintes

1 ≤ s.length ≤ 100
s ne contient que les chiffres 0 à 9, et peut commencer par 0.
Chaque préfixe et chaque suffixe de s possède moins de 2³¹ décodages, donc la réponse et tous les comptes calculés 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 se regroupent jamais par paires, 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 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 seul n’est pas une lettre et 06 n’est pas un code, donc aucun message ne donne cette chaîne.

Pour aller plus loin

Et si s pouvait aussi contenir *, qui représente n’importe quel chiffre de 1 à 9 ? Peux-tu compter les interprétations en O(n), 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 une lettre à lui seul ou se joint à son voisin, si bien que le nombre de lectures croît comme les nombres de Fibonacci : 45 uns donnent 1836311903. Il est impossible de les énumérer, mais les façons de terminer une lecture dépendent uniquement de la position atteinte, donc il suffit de compter chaque position une fois. Un 0 ne peut terminer que 10 ou 20.

Essayez les deux interprétations avec la récursion

Correcte, mais ne termine pas sur les plus gros tests

Intuition

À l’indice i, un 0 ne commence aucune lettre, donc le chemin ne donne aucune lecture. Sinon, lisez un chiffre et comptez le reste à partir de i+1 ; si les deux chiffres forment un nombre de 10 à 26, lisez aussi les deux et comptez à partir de i+2. Les deux choix donnent des premières lettres différentes, donc leurs nombres s’additionnent sans chevauchement, et atteindre la fin complète une lecture.

Rien n’est mémorisé, donc les appels suivent la règle de Fibonacci : 45 chiffres 1 prennent environ 5 × 10^9 appels. Une réponse de 0 n’est pas plus rapide : 44 chiffres 1, 55 chiffres 3 et un 0 final prennent environ 10^11 appels, car chaque lecture des chiffres 1 n’échoue qu’au dernier chiffre.

Algorithme

waysFrom(i) compte les lectures des chiffres à partir de l’indice i.
À la fin de la chaîne, renvoie 1. Pour un 0, renvoie 0.
Sinon, renvoie waysFrom(i+1), plus waysFrom(i+2) lorsque les chiffres i et i+1 forment un nombre inférieur ou égal à 26.
La réponse est 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)

La récursivité avec mémoïsation

Intuition

La récursion pose plusieurs fois la même question. Dans "11111", le nombre à 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. Stocke chaque nombre la première fois que tu le calcules et marque les emplacements pas encore calculés avec -1, puisque 0 est un nombre réel.

Il y a n positions, chacune calculée une seule fois avec un travail constant : temps O(n). La mémoïsation et la pile d’appels occupent un espace O(n), avec une profondeur maximale de 100 appels.

Algorithme

Remplissez memo avec -1, une case par index.
Dans waysFrom(i), renvoyez 1 à la fin de la chaîne et memo[i] lorsqu’il n’est pas égal à -1.
Sinon, comptez comme dans la récursion simple, enregistrez le compte dans memo[i], y compris zéro, puis renvoyez-le.

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

Comptez plutôt les préfixes. Soit ways(i) le nombre de lectures des i premiers chiffres. La dernière lettre correspond soit au chiffre i-1 seul, ce qui nécessite un chiffre de 1 à 9 et laisse ways(i-1) lectures, soit aux chiffres i-2 et i-1 ensemble, qui doivent former un nombre de 10 à 26 et laisser ways(i-2) lectures. Additionnez les contributions dont la condition est satisfaite. Le préfixe vide a une lecture, donc ways(0) = 1.

Pour "1203", les comptes passent à 1, puis 2, puis reviennent à 1 au 0, car seul 20 fonctionne et il laisse le compte d’avant le 2. Le 3 est seul, donc le compte reste à 1. Chaque compte dépend des deux positions précédentes, donc deux variables remplacent le tableau : temps en O(n), espace en O(1).

Algorithme

Définissez twoBack = 0 et oneBack = 1, le nombre pour le préfixe vide.
Pour chaque indice i, définissez current sur oneBack si le chiffre i n’est pas 0, sinon sur 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 : twoBack = oneBack, puis oneBack = current.
Retournez 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

Traiter 0 comme une lettre, ou 06 comme 6. "30", "100" et "06" ont tous 0 décodage.
Tester un morceau de deux chiffres avec seulement ≤ 26. 05 vaut 5 comme nombre, mais ne constitue pas un code : vérifie donc que son premier chiffre n’est pas 0.
Marquer les cases mémo inconnues avec 0. Les positions avec 0 décodage ne sont alors jamais comptées comme mémorisées : avec 44 uns, 55 trois et un 0 final, tu reviens à environ 10^11 appels.
Lire le chiffre avant l’index 0. Protège la vérification des deux chiffres avec i ≥ 1 ; en Python, s[-1] lit silencieusement le dernier chiffre.
Transformer s en un seul nombre. Une centaine de chiffres ne tient dans aucun type entier, et les zéros en tête qui changent la réponse sont perdus.

Questions fréquentes3

Quelle est la complexité temporelle de Decode Ways ?

La solution ascendante lit chaque chiffre une seule fois avec un travail constant : un temps O(n) et un espace supplémentaire O(1). La récursion avec mémoïsation prend également un temps O(n), mais utilise un espace O(n). La récursion simple est exponentielle : sur une chaîne composée de uns, le nombre d’appels croît comme 1.618^n.

Quel est le lien entre Decode Ways et Climbing Stairs ?

Les deux comptent le nombre de façons de parcourir une ligne avec des pas de 1 et de 2. Dans Climbing Stairs, chaque pas est autorisé, donc les décomptes sont les nombres 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 n’est donc ajouté que si sa condition est remplie.

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

Un 0 n’est jamais une lettre à lui seul, il doit donc s’associer au chiffre qui le précède, comme dans 10 ou 20. Il ajoute le décompte d’il y a deux chiffres uniquement après un 1 ou un 2, et rien dans les autres cas. Un 0 en tête, deux zéros à la suite ou un 0 après un chiffre de 3 à 9 donne 0.

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

Test #1

Test #2

Test #3

Argument

s = "2611"

Résultat attendu

Decode Ways

Fonction

Contraintes

Exemples

Indices

Solution

Essayez les deux interprétations avec la récursion

La récursivité avec mémoïsation

De bas en haut avec deux compteurs

Pièges et cas limites

Questions fréquentes3

Problèmes similaires