Vérifiez si une chaîne de parenthèses peut être valide

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

Difficulté :Moyen

Sujets : String, Stack, Greedy

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

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

Vous recevez une chaîne de parenthèses s et une chaîne verrouillée, toutes deux de longueur n. verrouillé est une chaîne binaire composée uniquement de « 0 » et de « 1 ». Pour chaque indice i de verrouillé,

• Si verrouillé[i] est '1', vous ne pouvez pas modifier s[i].
• Mais si verrouillé[i] est '0', vous pouvez remplacer s[i] par '(' ou ')'.

Renvoyer true si vous pouvez créer s une chaîne de parenthèses valide. Sinon, retournez false.

Exemple 1 :

• Entrée : s = "))()))", verrouillé = "010100"
• Sortie : 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é = "0000"
• Sortie : vrai
• Explication : Nous n'avons pas besoin d'apporter de modifications car s est déjà valide.

Exemple 3 :

• Entrée : s = ")", verrouillé = "0"
• Sortie : faux
• Explication : verrouillé nous permet de modifier s[0].
  • Changer s[0] par '(' ou ')' ne rendra pas s valide.

Contraintes :

• n == s.length == verrouillé.length
• 1 5
• s[i] est soit '(' ou ')'.
• verrouillé[i] est soit « 0 » soit « 1 ».

Indice :

1. Une chaîne de longueur impaire peut-elle être valide ?
2. De gauche à droite, si un ')' verrouillé est rencontré, il doit être équilibré avec soit un '(' verrouillé ou un index déverrouillé sur sa gauche. Si aucun des deux n'existe, quelle conclusion peut-on en tirer ? Si les deux existent, lequel est-il préférable d'utiliser ?
3. Après ce qui précède, nous avons peut-être verrouillé les index de '(' et des index déverrouillés supplémentaires. Comment pouvez-vous équilibrer les '(' verrouillés maintenant ? Que faire si vous ne parvenez pas à équilibrer les '(' verrouillés ?

Solution :

On peut l'aborder étape par étape, en gardant à l'esprit les contraintes et le comportement des positions verrouillées.

Points clés :

1. Si la longueur de la chaîne est impaire, nous pouvons immédiatement renvoyer false car une chaîne de parenthèses valide doit avoir une longueur paire (chaque ouverture ( nécessite une fermeture )).
2. Nous devons garder une trace du nombre de parenthèses ouvertes (() et de parenthèses fermées ()) lorsque nous parcourons la chaîne. Si à un moment donné le nombre de parenthèses fermantes dépasse le nombre de parenthèses ouvrantes, il est impossible d'équilibrer la chaîne et nous renvoyons false.
3. Nous devons gérer avec soin les positions qui sont verrouillées (locked[i] == '1') et déverrouillées (locked[i] == '0'). Les positions déverrouillées nous permettent de changer le personnage, mais pas les positions verrouillées.

Algorithme:

• Étape 1 : Vérifiez si la longueur de la chaîne s est impaire. Si tel est le cas, renvoyez false immédiatement.
• Étape 2 : Parcourez la chaîne de gauche à droite pour suivre l'équilibre des parenthèses.
  • Utilisez un compteur pour suivre l'équilibre entre les parenthèses ouvrantes (et fermantes).
  • Si à un moment donné, le nombre de parenthèses fermantes dépasse le nombre de parenthèses ouvrantes, vérifiez si les positions verrouillées ont suffisamment de flexibilité pour l'équilibrer.
  • Après avoir traité la chaîne entière, vérifiez si les parenthèses sont équilibrées, c'est-à-dire s'il ne reste pas de parenthèses ouvrantes sans correspondance.

Implémentons cette solution en PHP : 2116. Vérifiez si une chaîne de parenthèses peut être valide

<?php /**
 * @param String $s
 * @param String $locked
 * @return Boolean
 */
function canBeValid($s, $locked) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$s = "))()))";
$locked = "010100";
var_dump(canBeValid($s, $locked));  // Output: bool(true)

$s = "()()";
$locked = "0000";
var_dump(canBeValid($s, $locked));  // Output: bool(true)

$s = ")";
$locked = "0";
var_dump(canBeValid($s, $locked));  // Output: bool(false)
?>

Explication:

1. Premier passage (de gauche à droite) :

   • Nous parcourons la chaîne et suivons l'équilibre des parenthèses ouvertes. Chaque fois que l'on rencontre une parenthèse ouverte (, on incrémente le compteur ouvert. Pour une parenthèse fermée), on décrémente le compteur ouvert.
   • Si le caractère actuel est déverrouillé (locked[i] == '0'), nous pouvons supposer qu'il l'est (si nécessaire pour équilibrer les parenthèses.
   • Si à un moment donné le compteur ouvert devient négatif, cela signifie que nous avons plus de parenthèses fermantes que de parenthèses ouvertes, et nous renvoyons faux.

2. Deuxième passage (de droite à gauche) :

   • Nous effectuons une opération similaire en sens inverse pour gérer le scénario de parenthèses ouvrantes sans correspondance qui pourraient se trouver à la fin de la chaîne.
   • Ici, nous suivons les parenthèses fermantes ()) avec le compteur de fermeture et veillons à ce qu'aucune parenthèse déséquilibrée n'existe.

3. Edge Case : Si la longueur de la chaîne est impaire, nous renvoyons immédiatement false car elle ne peut pas former une chaîne de parenthèses valide.

Complexité temporelle :

• Les deux passes (de gauche à droite et de droite à gauche) prennent un temps linéaire, O(n), où n est la longueur de la chaîne. Ainsi, la complexité temporelle globale est O(n), ce qui est efficace pour les contraintes de taille d'entrée.

Cette solution gère correctement le problème dans les limites données.

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!