2116. Vérifier si une chaîne de parenthèses peut être valide

2116. Vérifier si une chaîne de parenthèses peut être valide

Difficulté : moyenne

Sujets :Chaîne,Empiler,Cupide

Une chaîne de parenthèses est unnon videchaîne composée uniquement de'('et')'. Il est valable si l'une des conditions suivantes estvrai:

• C'est().
• On peut l'écrire commeAB(UNconcaténé avecB), oùUNetBsont des chaînes de parenthèses valides.
• On peut l'écrire comme(UN), oùUNest une chaîne de parenthèses valide.

Vous recevez une chaîne de parenthèsesset une chaînefermé, tous deux de longueurn.ferméest une chaîne binaire composée uniquement de'0'sable'1's. Pour chaque indicejedefermé,

• Si verrouillé[je]est'1', tu ne peux pas changersi].
• Mais siverrouillé[i]est'0', tu peux changersi]soit à'('ou')'.

Retourvraisi tu peux fairesune chaîne de parenthèses valide. Sinon, retournezFAUX.

Exemple 1 :

• Entrée : s = "))()))", verrouillé = "010100"
• Résultat : vrai
• Explication : verrouillé[1] == '1' et verrouillé[3] == '1', nous ne pouvons donc pas changer s[1] ou s[3].
  • Nous changeons s[0] et s[4] en '(' tout en laissant s[2] et s[5] inchangés pour rendre s valide.

Exemple 2 :

• Entrée : s = "()()", verrouillé = "00...
  [Courte citation de 8% de l'article original]