Valid Parentheses

Q: Quelle est la complexité temporelle de Valid Parentheses ?

La solution avec une pile s’exécute en temps O(n) , puisque chaque caractère est empilé ou dépilé au plus une fois. Elle utilise un espace de O(n) dans le pire des cas, avec une chaîne composée uniquement de délimiteurs ouvrants. Supprimer les paires correspondantes encore et encore prend un temps de O(n²) , car une chaîne profondément imbriquée ne perd qu’une seule paire par tour.

FacilePile

+10

On te donne une chaîne s composée uniquement des caractères de parenthèses (, ), [, ], { et }. Renvoie true lorsque les parenthèses sont équilibrées : chaque parenthèse fermante ferme la parenthèse ouverte la plus récente, les deux sont du même type et aucune parenthèse ne reste ouverte à la fin. Sinon, renvoie false.

Fonction

isValid(s: string) → boolean

sstring: la chaîne de crochets à vérifier
Renvoieboolean: si les parenthèses sont équilibrées

Contraintes

1 ≤ s.length ≤ 10⁴
s ne contient que les caractères (, ), [, ], { et }.

Exemples

Entrée: s = "[]{}()"
Sortie: true
Explication: Trois paires se tiennent côte à côte, et chacune se ferme juste après s’être ouverte.

Entrée: s = "{(})"
Sortie: false
Explication: Le } arrive alors que la ( ouverte après celui-ci est toujours ouverte ; il ferme donc le mauvais type de crochet.

Pour aller plus loin

Si la chaîne ne contenait que des parenthèses rondes, pourrais-tu la vérifier avec un seul compteur au lieu d’une pile, en utilisant un espace supplémentaire de O(1) ?

Solution

Compter les parenthèses ne suffit pas : {(}) contient une parenthèse ouvrante et une parenthèse fermante de chaque type, mais reste incorrect, car l’ordre compte. Une pile conserve les parenthèses encore ouvertes dans l’ordre où elles ont été ouvertes ; un seul parcours avec une pile suffit donc à déterminer si toute la chaîne est correcte.

Supprimez à plusieurs reprises les paires correspondantes

Correcte, mais ne termine pas sur les plus gros tests

Intuition

Chaque chaîne équilibrée contient une paire la plus intérieure dont les crochets n’ont rien entre eux, comme () dans {[()]}. Supprimer une paire adjacente correspondante ne change jamais le fait qu’une chaîne soit équilibrée ou non. Répète donc les suppressions jusqu’à ce qu’un tour n’en supprime plus aucune : une chaîne équilibrée se réduit à une chaîne vide, tandis qu’une chaîne non équilibrée reste bloquée avec des caractères, comme c’est le cas dès le départ pour {(}).

Chaque tour parcourt la chaîne entière et construit une nouvelle copie, et une chaîne imbriquée comme (((...))) perd une paire par tour. Cela représente jusqu’à n/2 tours de travail en O(n), soit O(n²) au total.

Algorithme

Supprime toutes les occurrences de (), [] et {} dans la chaîne.
Si cette passe n’a rien supprimé, arrête-toi.
Sinon, recommence avec la chaîne raccourcie.
Renvoie true si la chaîne est devenue vide, et false s’il reste une parenthèse.

def isValid(s):
    while True:
        # Delete every adjacent matched pair in one round.
        shorter = s.replace("()", "").replace("[]", "").replace("{}", "")
        if shorter == s:
            break  # nothing left to delete
        s = shorter
    return s == ""

Un parcours avec une pile

Intuition

Une parenthèse fermante doit fermer la parenthèse ouverte la plus récemment qui est encore ouverte. La dernière parenthèse ouverte est la première à être fermée ; cet ordre dernier entré, premier sorti est précisément ce que garantit une pile.

Empilez le caractère fermant attendu pour chaque caractère ouvrant. Un caractère fermant doit alors correspondre au sommet de la pile. Une pile vide signifie qu’il n’y a rien à fermer ; un sommet différent signifie que le caractère ferme une parenthèse du mauvais type, comme le fait } dans {(}) alors que ) se trouve au sommet. À la fin, tout élément restant dans la pile, comme dans ((, a été ouvert et jamais fermé. Chaque caractère est empilé ou dépilé une seule fois : temps en O(n) et au plus n éléments dans la pile.

Algorithme

Crée une pile vide.
Pour une parenthèse ouvrante, empile sa parenthèse fermante correspondante.
Pour une parenthèse fermante, renvoie false si la pile est vide ou si son sommet est un caractère différent ; sinon, dépile.
Après le dernier caractère, renvoie true uniquement si la pile est vide.

def isValid(s):
    closers = {'(': ')', '[': ']', '{': '}'}
    stack = []
    for ch in s:
        if ch in closers:
            stack.append(closers[ch])
        elif not stack or stack.pop() != ch:
            return False
    return not stack

Pièges et cas limites

Compter chaque type de délimiteur. {(}) a le même nombre de chaque type et reste invalide, et )( est invalide uniquement à cause de l’ordre.
Dépiler un élément d’une pile vide. Une chaîne qui commence par un délimiteur fermant, comme } ou )]}, doit renvoyer false au lieu de provoquer une erreur.
Omettre la vérification finale. (([{ ne rencontre jamais de délimiteur fermant incorrect ; seule la pile restante permet donc de voir que la chaîne est invalide.
Se fier à la longueur. Une longueur impaire est toujours invalide, mais une longueur paire ne prouve rien : (] et ())( sont tous deux invalides.
Dans l’approche par suppression, passer des délimiteurs à une expression régulière ou à un motif Lua sans les échapper. ( et [ ont une signification dans ces expressions ; utilisez un remplacement en texte brut.

Questions fréquentes3

Quelle est la complexité temporelle de Valid Parentheses ?

La solution avec une pile s’exécute en temps O(n), puisque chaque caractère est empilé ou dépilé au plus une fois. Elle utilise un espace de O(n) dans le pire des cas, avec une chaîne composée uniquement de délimiteurs ouvrants. Supprimer les paires correspondantes encore et encore prend un temps de O(n²), car une chaîne profondément imbriquée ne perd qu’une seule paire par tour.

Pourquoi utilise-t-on une pile pour vérifier la validité des parenthèses ?

Les crochets s’imbriquent, donc le crochet ouvert en dernier doit être fermé en premier. Une pile garde ce crochet au sommet, où tu peux le consulter et le retirer en temps constant, ce qui maintient toute la vérification en O(n).

Une chaîne vide est-elle une séquence de parenthèses valide ?

Oui. Une chaîne vide ne contient aucun crochet sans correspondance, elle est donc équilibrée : la pile reste vide et la boucle de suppression n’a rien à supprimer. Dans ce problème, s contient toujours au moins un caractère.

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

Test #1

Test #2

Test #3

Argument

s = "[]{}()"

Résultat attendu

true