Inverser les sous-chaînes entre chaque paire de parenthèses

1190. Inverser les sous-chaînes entre chaque paire de parenthèses

Moyen

Vous recevez une chaîne s composée de lettres anglaises minuscules et de crochets.

Inversez les chaînes dans chaque paire de parenthèses correspondantes, en commençant par la plus intérieure.

Votre résultat ne doit ne contenir aucune parenthèse.

Exemple 1 :

• Entrée : s = "(abcd)"
• Sortie : "dcba"

Exemple 2 :

• Entrée : s = "(u(love)i)"
• Sortie : "iloveu"
• Explication : La sous-chaîne "love" est d'abord inversée, puis la chaîne entière est inversée.

Exemple 3 :

• Entrée : s = "(ed(et(oc))el)"
• Sortie : "leetcode"
• Explication : Tout d'abord, on inverse la sous-chaîne "oc", puis "etco", et enfin, la chaîne entière.

Contraintes :

• 1 <= s.length <= 2000
• s ne contient que des caractères anglais minuscules et des parenthèses.
• Il est garanti que toutes les parenthèses sont équilibrées.

Solution :

Voici le plan étape par étape :

1. Utilisez une pile pour garder une trace des caractères et des parenthèses imbriquées.
2. Parcourez chaque caractère de la chaîne.
3. Si vous rencontrez une parenthèse ouvrante '(', poussez-la sur la pile.
4. Si vous rencontrez une parenthèse fermante ')', sortez de la pile jusqu'à ce que vous atteigniez une parenthèse ouvrante '('. Inversez la sous-chaîne collectée et repoussez-la sur la pile.
5. Enfin, concaténez le contenu de la pile pour obtenir le résultat.

Voici l'implémentation en PHP : 1190. Inverser les sous-chaînes entre chaque paire de parenthèses

  
  
  Explication



La fonction reverseParentheses prend une chaîne s en entrée.
Une pile est utilisée pour garder une trace des caractères et des parenthèses imbriquées.
Lorsque nous parcourons la chaîne :


Si nous rencontrons une parenthèse fermante ), nous commençons à sortir de la pile jusqu'à ce que nous trouvions une parenthèse ouvrante (.
Nous collectons les caractères éclatés (qui se trouvent entre parenthèses), les inversons et les repoussons sur la pile.
Si le caractère n'est pas une parenthèse fermante, il est directement poussé sur la pile.





Enfin, nous concaténons les éléments de la pile pour former la chaîne résultat, en veillant à ce que les parenthèses ne soient pas incluses.



Cette méthode gère efficacement les parenthèses imbriquées et garantit le bon ordre des caractères après avoir inversé les sous-chaînes dans chaque paire de parenthèses.

Liens de contact


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!