. Ajout minimum pour rendre les parenthèses valides

921. Ajout minimum pour rendre les parenthèses valides

Difficulté :Moyen

Sujets : String, Stack, Greedy

Une chaîne de parenthèses est valide si et seulement si :

• C'est la chaîne vide,
• Il peut être écrit comme AB (A concaténé avec B), où A et B sont des chaînes valides, ou
• Il peut être écrit sous la forme (A), où A est une chaîne valide.

Vous recevez une chaîne de parenthèses s. D'un seul geste, vous pouvez insérer une parenthèse à n'importe quelle position de la chaîne.

• Par exemple, si s = "()))", vous pouvez insérer une parenthèse ouvrante pour être "(()))" ou une parenthèse fermante pour être "())))".

Renvoyer le nombre minimum de coups requis pour rendre les s valides.

Exemple 1 :

• Entrée : s = "())"
• Sortie : 1

Exemple 2 :

• Entrée : s = "((("
• Sortie : 3

Contraintes :

• 1 <= s.length <= 1000
• s[i] est soit '(' ou ')'.

Solution :

Nous devons déterminer combien de parenthèses ouvrantes ou fermantes doivent être ajoutées pour que la chaîne d'entrée soit valide. Une chaîne valide signifie que chaque parenthèse ouvrante '(' a une parenthèse fermante correspondante ')'.

Nous pouvons résoudre ce problème en utilisant une simple contre-approche :

• Nous utilisons un solde variable pour suivre le solde actuel entre les parenthèses ouvrantes et fermantes.
• Nous utilisons une autre variable d'ajout pour compter le nombre minimum de parenthèses requis.

Approche:

1. Parcourez chaque caractère de la chaîne s.
2. Si le caractère est '(', incrémentez le solde de 1.
3. Si le caractère est ')', décrémentez le solde de 1 :
   • Si le solde devient négatif, cela signifie qu'il y a plus de parenthèses fermantes que de parenthèses ouvrantes. Nous devons ajouter une parenthèse ouvrante pour l'équilibrer, donc incrémentez les ajouts de 1 et réinitialisez le solde à 0.
4. À la fin de la boucle, si le solde est supérieur à 0, cela indique qu'il y a des parenthèses ouvrantes sans correspondance, alors ajoutez le solde aux ajouts.

Implémentons cette solution en PHP : 921. Ajout minimum pour rendre les parenthèses valides

  
  
  Explication:



Pour la chaîne s = "())" :



le solde devient négatif lorsque le deuxième ')' est rencontré, donc les ajouts sont incrémentés.
À la fin, le solde est de 0 et les ajouts sont de 1, nous avons donc besoin de 1 ajout pour rendre la chaîne valide.





Pour la chaîne s = "(((":



le solde devient 3 car il y a 3 '(' sans correspondance à la fin.
Le résultat est le solde des additions, qui est 0 3 = 3.







Cette solution a une complexité temporelle de O(n) où n est la longueur de la chaîne et un espace complexité de O(1) puisque nous n'utilisons que quelques variables.

Liens de contact

Si vous avez trouvé cette série utile, pensez à donner une étoile au référentiel sur GitHub ou à partager la publication sur vos réseaux sociaux préférés ?. Votre soutien signifierait beaucoup pour moi !

Si vous souhaitez du contenu plus utile comme celui-ci, n'hésitez pas à me suivre :


LinkedIn
GitHub



          

            
  

            
        
Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!