Prüfen Sie, ob eine Klammerzeichenfolge gültig sein kann

2116. Prüfen Sie, ob eine Klammerzeichenfolge gültig sein kann

Schwierigkeit:Mittel

Themen:String, Stack, Greedy

Eine Klammerzeichenfolge ist eine nicht leere Zeichenfolge, die nur aus „(“ und „)“ besteht. Es ist gültig, wenn eine der folgenden Bedingungen zutrifft:

• Es ist ().
• Es kann als AB (A verkettet mit B) geschrieben werden, wobei A und B gültige Klammerzeichenfolgen sind.
• Es kann als (A) geschrieben werden, wobei A eine gültige Klammerzeichenfolge ist.

Sie erhalten eine Klammerzeichenfolge s und eine gesperrte Zeichenfolge, beide mit der Länge n. „locked“ ist eine binäre Zeichenfolge, die nur aus „0“ und „1“ besteht. Für jeden Index i von gesperrt,

• Wenn „locked[i]“ „1“ ist, können Sie s[i] nichtändern.
• Aber wenn „locked[i]“ „0“ ist, können Sie s[i] entweder in „(“ oder „)“ ändern.

Gib true zurück, wenn Sie s zu einer gültigen Klammerzeichenfolge machen können. Andernfalls geben Sie false zurück.

Beispiel 1:

• Eingabe: s = "))()))", locked = "010100"
• Ausgabe:wahr
• Erklärung: gesperrt[1] == '1' und gesperrt[3] == '1', daher können wir s[1] oder s[3] nicht ändern.
  • Wir ändern s[0] und s[4] in „(“, während wir s[2] und s[5] unverändert lassen, um s gültig zu machen.

Beispiel 2:

• Eingabe: s = "()()", locked = "0000"
• Ausgabe:wahr
• Erklärung: Wir müssen keine Änderungen vornehmen, da s bereits gültig ist.

Beispiel 3:

• Eingabe: s = ")", locked = "0"
• Ausgabe:false
• Erklärung: gesperrt erlaubt uns, s[0] zu ändern.
  • Das Ändern von s[0] in entweder „(“ oder „)“ führt dazu, dass s nicht gültig wird.

Einschränkungen:

• n == s.length == locked.length
• 1 5
• s[i] ist entweder '(' oder ')'.
• „locked[i]“ ist entweder „0“ oder „1“.

Hinweis:

1. Kann eine Zeichenfolge mit ungerader Länge jemals gültig sein?
2. Wenn von links nach rechts ein gesperrtes „)“ angetroffen wird, muss es entweder mit einem gesperrten „(“ oder einem nicht gesperrten Index auf der linken Seite ausgeglichen werden. Wenn keiner von beiden existiert, welche Schlussfolgerung kann gezogen werden? Wenn beide existieren, Welches ist besser zu verwenden?
3. Nach dem oben Gesagten haben wir möglicherweise gesperrte Indizes von „(“ und weitere nicht gesperrte Indizes. Wie können Sie die gesperrten „(“ jetzt ausgleichen? Was ist, wenn Sie keine gesperrten „(“ ausgleichen können?

Lösung:

Wir können Schritt für Schritt vorgehen und dabei die Einschränkungen und das Verhalten der gesperrten Positionen berücksichtigen.

Wichtige Punkte:

1. Wenn die Länge der Zeichenfolge ungerade ist, können wir sofort false zurückgeben, da eine gültige Klammerzeichenfolge eine gerade Länge haben muss (jede Öffnung (benötigt eine Schließung)).
2. Wir müssen die Anzahl der offenen Klammern (() und geschlossenen Klammern ()) im Auge behalten, während wir die Zeichenfolge durchlaufen. Wenn zu irgendeinem Zeitpunkt die Anzahl der schließenden Klammern die Anzahl der öffnenden Klammern übersteigt, ist es unmöglich, die Zeichenfolge auszugleichen, und wir geben „false“ zurück.
3. Wir müssen sorgfältig mit den Positionen umgehen, die gesperrt (locked[i] == '1') und entsperrt (locked[i] == '0') sind. Bei entsperrten Positionen können wir den Charakter ändern, bei gesperrten Positionen jedoch nicht.

Algorithmus:

• Schritt 1: Überprüfen Sie, ob die Länge der Zeichenfolge s ungerade ist. Wenn ja, geben Sie sofort false zurück.
• Schritt 2: Durchlaufen Sie die Zeichenfolge von links nach rechts, um das Gleichgewicht der Klammern zu verfolgen.
  • Verwenden Sie einen Zähler, um das Gleichgewicht zwischen öffnenden (und schließenden) Klammern zu verfolgen.
  • Wenn zu irgendeinem Zeitpunkt die Anzahl der schließenden Klammern die der öffnenden Klammern übersteigt, prüfen Sie, ob die gesperrten Positionen genügend Flexibilität haben, um dies auszugleichen.
  • Überprüfen Sie nach der Verarbeitung der gesamten Zeichenfolge, ob die Klammern ausgeglichen sind, d. h. ob keine nicht übereinstimmenden öffnenden Klammern übrig geblieben sind.

Lassen Sie uns diese Lösung in PHP implementieren: 2116. Prüfen Sie, ob eine Klammerzeichenfolge gültig sein kann

<?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)
?>

Erläuterung:

1. Erster Durchgang (von links nach rechts):

   • Wir durchlaufen die Zeichenfolge und verfolgen den Rest der offenen Klammern. Jedes Mal, wenn wir auf eine offene Klammer stoßen (, erhöhen wir den offenen Zähler. Bei einer geschlossenen Klammer dekrementieren wir den offenen Zähler.
   • Wenn das aktuelle Zeichen entsperrt ist (locked[i] == '0'), können wir davon ausgehen, dass es ( falls erforderlich, um die Klammern auszugleichen.
   • Wenn der offene Zähler zu irgendeinem Zeitpunkt negativ wird, bedeutet das, dass wir mehr schließende als öffnende Klammern haben und wir geben false zurück.

2. Zweiter Durchgang (von rechts nach links):

   • Wir führen einen ähnlichen Vorgang in umgekehrter Reihenfolge durch, um das Szenario nicht übereinstimmender öffnender Klammern zu bewältigen, die möglicherweise am Ende der Zeichenfolge stehen.
   • Hier verfolgen wir schließende Klammern ()) mit dem Schließzähler und stellen sicher, dass keine unausgeglichenen Klammern vorhanden sind.

3. Edge Case: Wenn die Zeichenfolgenlänge ungerade ist, geben wir sofort false zurück, da sie keine gültige Klammerzeichenfolge bilden kann.

Zeitkomplexität:

• Beide Durchläufe (von links nach rechts und von rechts nach links) benötigen eine lineare Zeit, O(n), wobei n die Länge der Zeichenfolge ist. Somit beträgt die Gesamtzeitkomplexität O(n), was für die Eingabegrößenbeschränkungen effizient ist.

Diese Lösung behandelt das Problem innerhalb der gegebenen Einschränkungen korrekt.

Kontaktlinks

Wenn Sie diese Serie hilfreich fanden, denken Sie bitte darüber nach, dem Repository einen Stern auf GitHub zu geben oder den Beitrag in Ihren bevorzugten sozialen Netzwerken zu teilen? Ihre Unterstützung würde mir sehr viel bedeuten!

Wenn Sie weitere hilfreiche Inhalte wie diesen wünschen, folgen Sie mir gerne:

• LinkedIn
• GitHub

Das obige ist der detaillierte Inhalt vonPrüfen Sie, ob eine Klammerzeichenfolge gültig sein kann. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!