. Minimale Hinzufügung, um Klammern gültig zu machen

921. Mindestanzahl hinzufügen, um Klammern gültig zu machen

Schwierigkeit:Mittel

Themen:String, Stack, Greedy

Eine Klammerzeichenfolge ist genau dann gültig, wenn:

• Es ist die leere Zeichenfolge,
• Es kann als AB (A verkettet mit B) geschrieben werden, wobei A und B gültige Zeichenfolgen sind, oder
• Es kann als (A) geschrieben werden, wobei A eine gültige Zeichenfolge ist.

Sie erhalten eine Klammerzeichenfolge s. Mit einem Zug können Sie an jeder beliebigen Stelle der Zeichenfolge eine Klammer einfügen.

• Wenn beispielsweise s = „()))“ ist, können Sie eine öffnende Klammer als „(()))“ oder eine schließende Klammer als „())))“ einfügen.

Gib die Mindestanzahl an Zügen zurück, die erforderlich sind, um s gültig zu machen.

Beispiel 1:

• Eingabe: s = "())"
• Ausgabe: 1

Beispiel 2:

• Eingabe: s = "((("
• Ausgabe: 3

Einschränkungen:

• 1 <= s.length <= 1000
• s[i] ist entweder '(' oder ')'.

Lösung:

Wir müssen bestimmen, wie viele öffnende oder schließende Klammern hinzugefügt werden müssen, damit die Eingabezeichenfolge gültig ist. Eine gültige Zeichenfolge bedeutet, dass jede öffnende Klammer „(“ eine entsprechende schließende Klammer „)“ hat.

Wir können dieses Problem mit einem einfachen Gegenansatz lösen:

• Wir verwenden einen variablen Saldo, um den aktuellen Saldo zwischen öffnenden und schließenden Klammern zu verfolgen.
• Wir verwenden weitere Variablenzusätze, um die Mindestanzahl der erforderlichen Klammern zu zählen.

Ansatz:

1. Durchlaufen Sie jedes Zeichen der Zeichenfolge s.
2. Wenn das Zeichen „(“ ist, erhöhen Sie den Kontostand um 1.
3. Wenn das Zeichen „)“ ist, verringern Sie den Kontostand um 1:
   • Wenn der Saldo negativ wird, bedeutet das, dass es mehr schließende als öffnende Klammern gibt. Wir müssen eine öffnende Klammer hinzufügen, um das Gleichgewicht auszugleichen. Erhöhen Sie also die Additionen um 1 und setzen Sie das Gleichgewicht auf 0 zurück.
4. Wenn der Saldo am Ende der Schleife größer als 0 ist, bedeutet dies, dass nicht übereinstimmende öffnende Klammern vorhanden sind. Addieren Sie also den Saldo zu den Ergänzungen.

Lassen Sie uns diese Lösung in PHP implementieren: 921. Mindestanzahl hinzufügen, um Klammern gültig zu machen

  
  
  Erläuterung:



Für die Zeichenfolge s = "())":



Der Saldo wird negativ, wenn das zweite „)“ auftritt, sodass die Additionen erhöht werden.
Am Ende beträgt der Saldo 0 und die Additionen 1, sodass wir 1 Addition benötigen, um die Zeichenfolge gültig zu machen.





Für die Zeichenfolge s = "(((":



Der Saldo beträgt 3, da am Ende 3 nicht übereinstimmende „(“ vorhanden sind.
Das Ergebnis ist der Additionssaldo, der 0 3 = 3 beträgt.







Diese Lösung hat eine zeitliche Komplexität von O(n), wobei n die Länge der Zeichenfolge und ein Leerzeichen ist Komplexität von O(1), da wir nur wenige Variablen verwenden.

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 von. Minimale Hinzufügung, um Klammern gültig zu machen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!