Valid Parentheses

Description

[EN]

You are given a string s consisting of the following characters: '(', ')', '{', '}', '[' and ']'. The input string s is valid if and only if:

1. Every open bracket is closed by the same type of close bracket.

2. Open brackets are closed in the correct order.

3. Every close bracket has a corresponding open bracket of the same type.

Return true if s is a valid string, and false otherwise.

[FR]

Une chaîne de caractères s est composée des symboles suivants : '(', ')', '{', '}', '[' et ']'. La chaîne s est considérée comme valide si et seulement si les conditions suivantes sont respectées :

1. Chaque parenthèse ouvrante a une parenthèse fermante du même type.

2. Les parenthèses ouvrantes sont fermées dans le bon ordre.

3. Chaque parenthèse fermante a une parenthèse ouvrante correspondante du même type.

Objectif :
Renvoyer true si la chaîne s est valide, et false sinon.

Approche: Utilisation d'une pile

Pour résoudre ce problème, je suis passé par l'utilisation d'une pile

• Logique : on effectue un parcours de la chaîne de caractère passée en paramètre. Pour chaque caractère, on vérifie s'il s'agit d'une parenthèse fermante

  • Dans le cas où on a une parenthèse fermante, on vérifie si le haut de la pile est une parenthèse ouvrante correspondante, et on la dépile le cas échéant.

  • Dans le cas contraire, on empile le caractère.

• A la fin de cette boucle, si notre pile est vide, cela signifie que l'on a une parenthèse valide, sinon, la parenthèse est invalide

• Complexité temporelle : Avec une boucle,la complexité temporelle est de O(n)

• Complexité spatiale : l'utilisation d'une pile nécessite un espace supplémentaire et donc la complexité spatiale est de O(n)