Decode String

Q: Pourquoi la pile stocke-t-elle le texte qui précédait chaque crochet ?

Lorsqu’un [ ouvre un groupe, le texte déjà décodé à ce niveau n’est pas terminé : les copies du groupe doivent encore être ajoutées après. L’empiler permet de le conserver pendant que tu décode le corps à partir d’une chaîne vide. Lorsque le ] correspondant arrive, le dépiler restitue ce texte et tu y ajoutes les copies.

MoyenPile Récursivité

+10

Une chaîne encodée représente un texte répété sous la forme k[text], ce qui signifie que text est écrit k fois à la suite. Les groupes peuvent être imbriqués, ainsi 2[a3[b]] signifie abbbabbb. Écris une fonction qui reçoit une chaîne encodée s et renvoie la chaîne décodée.

Les lettres situées en dehors de toutes les crochets restent inchangées. Chaque nombre de répétitions est un entier positif écrit juste avant son [, et les chiffres n'apparaissent nulle part ailleurs.

Fonction

decodeString(s: string) → string

sstring: la chaîne encodée
Renvoiestring: la chaîne décodée

Contraintes

1 ≤ s.length ≤ 10⁴
s contient uniquement des lettres minuscules anglaises, des chiffres, [ et ].
s est un encodage valide : chaque [ suit un compte et possède un ] correspondant, et aucune paire de crochets n'est vide.
Chaque nombre k vérifie 1 ≤ k ≤ 300 et ne comporte aucun zéro initial.
Les crochets peuvent s’imbriquer sur 100 niveaux de profondeur au maximum.
La chaîne décodée comporte au plus 5 × 10⁴ caractères.

Exemples

Entrée: s = "2[ab]3[c]x"
Sortie: "ababcccx"
Explication: 2[ab] donne abab et 3[c] donne ccc. Le x se trouve en dehors de toutes les parenthèses, il est donc recopié tel quel, ce qui donne ababcccx.

Entrée: s = "2[x3[yz]]"
Sortie: "xyzyzyzxyzyzyz"
Explication: Décode d’abord l’intérieur : 3[yz] correspond à yzyzyz, donc le contenu du groupe extérieur est xyzyzyz. Répété deux fois, cela donne xyzyzyzxyzyzyz.

Entrée: s = "q10[w]e"
Sortie: "qwwwwwwwwwwe"
Explication: Le décompte est de 10, lu à partir de deux chiffres, donc w apparaît dix fois entre q et e. Le code qui ne lit que le chiffre à côté de [ le répéterait 0 fois.

+22 tests cachés à la soumission

Pour aller plus loin

La chaîne décodée peut être bien plus longue que l’entrée. Comment renverrais-tu uniquement le caractère à la position i de la chaîne décodée, sans la construire, alors que sa longueur peut atteindre 10^18 ?

Indices

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

0 sur 3 ouverts

Solution

Le nombre vient avant les crochets, mais tu ne peux pas écrire les copies tant que tu ne sais pas ce qu’ils contiennent, et leur contenu peut lui-même contenir d’autres groupes. Un groupe ne peut donc être développé qu’une fois que tous les groupes qu’il contient sont terminés. Chaque approche ci-dessous permet de terminer d’abord les groupes les plus internes : réécrire la chaîne de l’intérieur vers l’extérieur, laisser un appel récursif terminer le groupe interne avant le groupe externe, ou conserver les groupes externes inachevés dans une pile. Ci-dessous, n est la longueur de l’entrée, m celle de la chaîne décodée et d la profondeur d’imbrication maximale.

Développez le groupe le plus interne, puis répétez

Intuition

Décodez la chaîne comme vous le feriez sur papier. Trouvez un groupe qui n’en contient aucun autre, écrivez ses répétitions à sa place, puis recommencez. Dans 2[x3[yz]], le groupe 3[yz] ne contient rien, donc la chaîne devient 2[xyzyzyz], et une expansion supplémentaire donne la réponse.

Le premier ] de la chaîne ferme toujours un tel groupe. Aucun autre groupe ne s’est fermé avant lui, donc rien entre lui et son [ ne peut être un crochet. Ce [ est le plus proche à sa gauche, et le nombre correspond à la suite de chiffres qui le précède immédiatement. Remplacez le nombre, les crochets et le contenu par le contenu répété k fois, puis recommencez jusqu’à ce qu’il ne reste plus de ].

C’est correct, mais chaque expansion reconstruit la chaîne entière. Avec b groupes et une chaîne qui s’allonge jusqu’à m caractères, cela représente jusqu’à b × m copies de caractères. Le test caché avec environ 1 300 groupes côte à côte nécessite environ 25 millions de copies pour produire 27 688 caractères, alors qu’un seul parcours de l’entrée suffirait.

Algorithme

Trouvez le premier ] dans la chaîne. S’il n’y en a pas, la chaîne est décodée : renvoyez-la.
Parcourez la chaîne vers la gauche depuis ce caractère jusqu’au [ le plus proche. Le texte entre les deux constitue le contenu du groupe.
Continuez vers la gauche au-delà des chiffres précédant ce [ et lisez-les comme le nombre k.
Remplacez tout le texte depuis le premier chiffre jusqu’au ] par le contenu du groupe répété k fois.
Revenez à l’étape 1.

def decodeString(s):
    # Expand one innermost group at a time until no bracket is left.
    while True:
        close = s.find("]")
        if close == -1:
            return s
        # The first ']' closes a group with no group inside it,
        # and the nearest '[' to its left opens that group.
        open_ = s.rfind("[", 0, close)
        start = open_
        while start > 0 and s[start - 1].isdigit():
            start -= 1
        times = int(s[start:open_])
        s = s[:start] + s[open_ + 1:close] * times + s[close + 1:]

Descente récursive

Intuition

Le format est récursif : une chaîne encodée est une séquence de lettres et de groupes, et le contenu d’un groupe est lui-même une chaîne encodée. Écris donc une seule fonction, decode, qui lit à partir d’une position partagée jusqu’à rencontrer le ] qui termine son niveau ou la fin de l’entrée, puis renvoie ce qu’elle a lu, décodé.

Lorsque decode rencontre un chiffre, elle lit le nombre entier, passe le [ et s’appelle elle-même pour décoder le contenu. Cet appel s’arrête au ] correspondant, car tout ] plus profond a déjà été consommé par un appel plus profond. L’appelant passe le ], ajoute le contenu k fois et continue la lecture. Pour 2[x3[yz]], l’appel externe lit 2 ; l’appel suivant lit x et 3 ; un troisième appel renvoie yz ; l’appel intermédiaire renvoie xyzyzyz ; et l’appel externe l’écrit deux fois.

Chaque caractère de l’entrée est lu une fois. Le coût réel vient des copies : un caractère de sortie est copié une fois pour chaque groupe qui l’entoure, donc le temps d’exécution est O(n + m·d) pour une profondeur d’imbrication d. La récursion atteint également d appels de profondeur. Cela convient pour 100 niveaux, mais une entrée très profondément imbriquée peut faire déborder la pile d’appels : Python, par exemple, s’arrête par défaut à 1 000 appels imbriqués.

Algorithme

Gardez une position pos, partagée par chaque appel, qui commence au premier caractère.
decode() boucle tant que pos se trouve dans la chaîne et n'est pas sur un ].
Sur une lettre, ajoutez-la et passez à la suite.
Sur un chiffre, lisez le nombre entier k, ignorez le [, appelez decode() pour le contenu, ignorez le ] et ajoutez le contenu k fois.
Renvoie ce qui a été construit. Le premier appel renvoie la chaîne décodée.

def decodeString(s):
    pos = 0

    def decode():
        # Read from pos up to the ']' that closes this level, or the end.
        nonlocal pos
        parts = []
        while pos < len(s) and s[pos] != "]":
            if s[pos].isdigit():
                times = 0
                while s[pos].isdigit():
                    times = times * 10 + int(s[pos])
                    pos += 1
                pos += 1          # skip '['
                inner = decode()  # the group's body, fully decoded
                pos += 1          # skip ']'
                parts.append(inner * times)
            else:
                parts.append(s[pos])
                pos += 1
        return "".join(parts)

    return decode()

Un seul passage avec une pile

Intuition

La récursion conserve un fragment de texte inachevé par groupe ouvert dans ses cadres d’appel. Tu peux plutôt conserver ces fragments dans ta propre pile et lire la chaîne en une seule boucle.

Pour le niveau actuel, suis deux éléments : current, le texte décodé jusqu’ici, et count, le nombre en cours de lecture. Un chiffre prolonge count selon la formule count × 10 + digit, ce qui permet d’obtenir correctement 10 et 300. Un [ ouvre un niveau : empile current et count, puis réinitialise les deux. Une lettre s’ajoute à current. Un ] ferme le niveau : dépile le texte et le nombre sauvegardés, et current devient le texte sauvegardé suivi de count copies de current.

Suivons 2[x3[yz]]. Au premier [, tu empiles (vide, 2). Le x donne à current la valeur x. Au deuxième [, tu empiles (x, 3) et yz remplit un nouveau current. Le premier ] dépile (x, 3), donc current devient xyzyzyz. Le dernier ] dépile (vide, 2), et current devient xyzyzyzxyzyzyz.

Les groupes se ferment dans l’ordre inverse de leur ouverture, donc le sommet de la pile correspond toujours au niveau auquel ] revient. Le travail est équivalent à celui de la récursion, O(n + m·d), mais un imbrication profonde ne fait qu’agrandir une liste, jamais la pile d’appels.

Algorithme

Commencez avec une pile vide, un current vide et count = 0.
Lorsqu’un chiffre apparaît, définissez count = count × 10 + digit.
À [, empilez la paire (current, count), puis réinitialisez current à vide et count à 0.
Lorsqu’une lettre apparaît, ajoutez-la à current.
À ], dépilez (before, k) et définissez current sur before suivi de k copies de current.
Après le dernier caractère, renvoyez current.

def decodeString(s):
    stack = []      # one entry per open '[': (the text before it, its count)
    current = []    # pieces of the text at the current level
    count = 0
    for ch in s:
        if ch.isdigit():
            count = count * 10 + int(ch)   # counts can have several digits
        elif ch == "[":
            stack.append((current, count))
            current, count = [], 0
        elif ch == "]":
            before, times = stack.pop()
            before.append("".join(current) * times)
            current = before
        else:
            current.append(ch)
    return "".join(current)

Pièges et cas limites

La plupart des mauvaises réponses viennent d’une mauvaise lecture du compteur ou d’une erreur sur l’endroit où le texte sauvegardé est placé.

Lire un seul chiffre comme s’il s’agissait du compteur entier. Dans q10[w]e, le compteur vaut 10. Un code qui ne prend que le chiffre avant le [ répète w 0 fois.
Oublier de remettre count à 0 après l’avoir empilé. Les chiffres du groupe suivant sont alors ajoutés à l’ancien nombre, si bien que 2[a3[b]] interprète le compteur interne comme étant 23.
Placer les copies avant le texte sauvegardé. À la lecture d’un ], le résultat est le texte précédant le groupe, suivi des copies : ab2[c] donne donc abcc, et non ccab.
Perdre des lettres au niveau supérieur. Le x dans 2[ab]3[c]x est à l’extérieur de toutes les crochets et doit tout de même figurer dans la réponse.
Ajouter les caractères un par un à une longue chaîne immuable. Chaque ajout peut recopier toute la chaîne, ce qui transforme une réponse de 50,000 caractères en milliards de copies. Rassemblez les morceaux dans une liste ou un constructeur de chaînes.

Questions fréquentes4

Quelle est la complexité temporelle de Decode String ?

La lecture de l’entrée est en O(n). La construction de la sortie copie chaque caractère une fois pour chaque groupe auquel il appartient ; le coût total est donc O(n + m·d), où m est la longueur décodée et d la profondeur d’imbrication. Lorsque chaque compte est au moins égal à 2, chaque groupe représente au plus la moitié de la longueur du groupe qui l’entoure, donc le nombre de copies reste inférieur à 2m. Aucune approche ne peut faire mieux que O(m), car la réponse elle-même comporte m caractères.

Faut-il résoudre Decode String avec la récursion ou avec une pile ?

Les deux font le même travail. La récursion suit directement le format, puisque le corps d’un groupe est lui-même une chaîne encodée, et c’est souvent la solution la plus rapide à écrire lors d’un entretien. La version avec pile fait la même chose dans une seule boucle et conserve les niveaux extérieurs inachevés dans une liste, afin qu’un imbrication très profonde ne provoque pas de dépassement de la pile d’appels. Si l’intervieweur pose une question sur une entrée imbriquée sur des milliers de niveaux, la pile est la réponse.

Comment gérer les nombres de plusieurs chiffres ?

Construisez le nombre au fur et à mesure que vous le lisez : partez de 0 et, pour chaque chiffre, définissez count = count × 10 + digit. Lorsque [ arrive, le nombre est complet, donc 300[a] donne 300. Réinitialisez le compteur à 0 dès que vous l’empilez, sinon les chiffres du groupe suivant s’y ajouteront.

Pourquoi la pile stocke-t-elle le texte qui précédait chaque crochet ?

Lorsqu’un [ ouvre un groupe, le texte déjà décodé à ce niveau n’est pas terminé : les copies du groupe doivent encore être ajoutées après. L’empiler permet de le conserver pendant que tu décode le corps à partir d’une chaîne vide. Lorsque le ] correspondant arrive, le dépiler restitue ce texte et tu y ajoutes les copies.

Python

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

Cas de test

Cas 1

Cas 2

Cas 3

Entrée

s = "2[ab]3[c]x"

Attendu

"ababcccx"

Decode String

Fonction

Contraintes

Exemples

Indices

Solution

Développez le groupe le plus interne, puis répétez

Descente récursive

Un seul passage avec une pile

Pièges et cas limites

Questions fréquentes4

Problèmes similaires