Longest Valid Parentheses

Q: Gibt es eine Lösung mit dynamischer Programmierung für „Longest Valid Parentheses“?

Ja. Sei end[i] die Länge der längsten korrekt gebildeten Teilzeichenkette, die am Index i endet; sie ist 0, wenn s[i] ( ist. Wenn s[i-1] ( ist, gilt end[i] = end[i-2] + 2 . Wenn es ) ist, betrachten wir j = i - end[i-1] - 1 , das Zeichen vor dem Lauf, der bei i-1 endet: Ist s[j] ( , schließt es diesen Lauf ein, und end[i] = end[i-1] + 2 + end[j-1] , wobei der letzte Term einen Lauf hinzufügt, der links daran anschließt. Die Antwort ist der größte Wert von end[i] , bei einer Zeit- und Speicherkomplexität von O(n) .

SchwerStack Dynamische Programmierung

+10

Du erhältst eine Zeichenfolge s, die nur aus den Zeichen ( und ) besteht. Finde die längste zusammenhängende Teilzeichenfolge (eine Folge aufeinanderfolgender Zeichen), die korrekt geklammert ist: Jede darin enthaltene ( wird durch ein späteres ) darin geschlossen, und die Klammerpaare sind korrekt verschachtelt, wie bei (()()). Gib die Länge dieser Teilzeichenfolge zurück oder 0, wenn nicht einmal () vorkommt.

Funktion

longestValidParentheses(s: string) → integer

sstring: eine Zeichenfolge aus ( und )-Zeichen
Gibt zurückinteger: die Länge der längsten wohlgeformten Teilzeichenfolge oder 0, falls es keine gibt

Einschränkungen

1 ≤ s.length ≤ 6 × 10⁴
Jedes Zeichen von s ist ( oder ).

Beispiele

Eingabe: s = "()(())"
Ausgabe: 6
Erklärung: Die gesamte Zeichenfolge ist wohlgeformt: () gefolgt von (()). Zwei wohlgeformte Teile nebeneinander ergeben einen wohlgeformten Teil, also besteht die Antwort aus allen 6 Zeichen.

Eingabe: s = "())((())"
Ausgabe: 4
Erklärung: Das ) am Index 2 hat kein Gegenstück, daher kann keine Lösung darüber hinausgehen, und das ( am Index 3 wird nie geschlossen. Das längste Teilstück ist (()) von Index 4 bis 7 mit der Länge 4 und damit länger als das () am Anfang.

Eingabe: s = "))(("
Ausgabe: 0
Erklärung: Beide ) kommen vor beiden (, daher wird kein ( jemals geschlossen. Kein Teilstring ist wohlgeformt und die Antwort ist 0.

+21 versteckte Tests beim Einreichen

Weiterführende Frage

Kannst du auch angeben, wo die längste wohlgeformte Teilzeichenfolge beginnt, und dabei die am weitesten links stehende auswählen, wenn mehrere dieselbe Länge haben?

Tipps

Öffne sie nacheinander. Jeder verrät ein bisschen mehr.

0 von 3 geöffnet

Lösung

Zwei Dinge machen dies schwieriger, als nur einen String zu prüfen. Korrekt geformte Teile verbinden sich, wenn sie aneinandergrenzen, sodass () und (()) nebeneinander als ein zusammenhängender Abschnitt der Länge 6 zählen. Und ein einzelnes überzähliges Zeichen, etwa das ) in ())(()), unterbricht den String, sodass keine Lösung darüber hinweggeht. Jeden Startpunkt zu testen kostet O(n²). Die Lösung besteht darin, sich zu merken, wo der aktuelle Abschnitt begann: Ein Stapel mit Indizes und einem Basis-Marker am unteren Ende erledigt das in einem Durchlauf, und zwei Durchläufe mit einfachen Zählern kommen ganz ohne Stapel aus.

Erzeuge eine Teilzeichenfolge ab jeder Startposition

Korrekt, wird aber bei den größten Tests nicht fertig

Idee

Lies eine Teilzeichenkette von links nach rechts und führe dabei einen Zähler, der für ( um 1 erhöht und für ) um 1 verringert wird. Die Teilzeichenkette ist genau dann korrekt geformt, wenn der Zähler nie unter 0 fällt und am Ende 0 beträgt. Ein Wert unter 0 bedeutet, dass ein ) eintrifft, ohne dass eine öffnende Klammer vorhanden ist, die es schließen könnte.

Lege also einen Startpunkt fest und gehe nach rechts, wobei du den Zähler Zeichen für Zeichen aktualisierst. Jedes Mal, wenn er wieder 0 erreicht, ist der Abschnitt vom Startpunkt bis hierher korrekt geformt, und du hältst seine Länge fest. Sobald er unter 0 fällt, brich ab: Dieses ) bleibt in jedem längeren Abschnitt ab diesem Startpunkt ungepaart. Jede korrekt geformte Teilzeichenkette hat einen Startpunkt, und du probierst dafür jedes mögliche Ende aus, sodass nichts übersehen wird.

Das Problem ist der Aufwand. In einer Zeichenkette aus 59998 (, gefolgt von (), fällt der Zähler nie unter 0, sodass jeder Startpunkt bis zum Ende durchläuft: etwa n²/2 = 1.8 × 10^9 Schritte für n = 6 × 10^4. Die großen Tests sind so aufgebaut. (Jede Teilzeichenkette von Grund auf neu zu prüfen, statt sie schrittweise zu erweitern, wäre noch schlimmer: O(n³).)

Algorithmus

Setze best auf 0.
Gehe jeden Start durch, setze balance auf 0 und gehe vom Start bis zum letzten Zeichen über das Ende.
Addiere 1 für ( und subtrahiere 1 für ).
Wenn balance kleiner als 0 ist, stoppe diesen Start. Wenn es 0 ist, aktualisiere best mit der Länge des Abschnitts end - start + 1.
Gib best zurück.

def longestValidParentheses(s):
    best = 0
    for start in range(len(s)):
        balance = 0
        for end in range(start, len(s)):
            balance += 1 if s[end] == "(" else -1
            if balance < 0:
                # A ')' without a partner: no longer run starts here
                break
            if balance == 0:
                best = max(best, end - start + 1)
    return best

Stapel von Indizes mit einer Basis-Markierung

Idee

Das Abgleichen von Klammern mithilfe eines Stacks ist vertraut: Lege für jedes ( ein Element auf den Stack und nimm für jedes ) eines herunter. Hier brauchst du außerdem Längen, also legst du Indizes auf den Stack und behältst ganz unten ein zusätzliches Element: die Basis, also die Position direkt vor dem zusammenhängenden Abschnitt, in dem du dich befindest. Am Anfang wurde noch nichts gelesen, daher ist die Basis -1.

Bei ( legst du seinen Index auf den Stack. Bei ) nimmst du ein Element herunter. Dabei kann zweierlei passieren. Wenn der Stack jetzt leer ist, hast du die Basis heruntergenommen. Dieses ) hatte also keine öffnende Klammer. Kein wohlgeformter Teilstring kann es enthalten, und es wird zur neuen Basis: Lege seinen Index auf den Stack. Andernfalls ist der oben verbliebene Index das letzte Zeichen vor dem Abschnitt, der bei i endet: entweder ein noch offenes ( oder die Basis. Alles danach bis einschließlich i ist abgeglichen, und der Abschnitt kann nicht weiter nach links reichen; seine Länge ist also i - top.

Hier ist ())((()):

i = 0, (: Lege 0 auf den Stack. Stack [-1, 0].
i = 1, ): Nimm 0 herunter. Oben liegt -1, der Abschnitt ist also 1 - (-1) = 2.
i = 2, ): Nimm -1 herunter, und der Stack ist leer. Dieses ) hat keine passende Klammer, also lege 2 als neue Basis auf den Stack. Stack [2].
i = 3, 4, 5, drei (: Lege sie auf den Stack. Stack [2, 3, 4, 5].
i = 6, ): Nimm 5 herunter. Oben liegt 4, der Abschnitt ist also 6 - 4 = 2.
i = 7, ): Nimm 4 herunter. Oben liegt 3, der Abschnitt ist also 7 - 3 = 4, die Antwort.

Die Basis sorgt dafür, dass aneinandergrenzende Teile zusammengezählt werden. Bei ()(()) ergibt das erste Klammerpaar 1 - (-1) = 2, und die letzte ) nimmt Index 2 herunter und findet wieder -1 oben, sodass sie 5 - (-1) = 6 ergibt. Würdest du stattdessen vom passenden ( aus messen, käme 4 heraus, und das vorangestellte () würde nicht mitgezählt. Jeder Index wird höchstens einmal auf den Stack gelegt und einmal heruntergenommen, daher ist der Durchlauf O(n), und der Stack kann bis zu n+1 Indizes enthalten.

Algorithmus

Beginne mit einem Stapel, der -1 enthält, und setze best auf 0.
Füge für jeden Index i den Wert i hinzu, wenn s[i] ( ist.
Wenn es ) ist, entferne einmal das oberste Element.
Wenn der Stapel jetzt leer ist, füge i als neue Basis hinzu. Andernfalls aktualisiere best mit i - top.
Gib best zurück.

def longestValidParentheses(s):
    # The bottom of the stack is the index just before the current run
    stack = [-1]
    best = 0
    for i, ch in enumerate(s):
        if ch == "(":
            stack.append(i)
        else:
            stack.pop()
            if not stack:
                # This ')' has no partner: it becomes the new base
                stack.append(i)
            else:
                best = max(best, i - stack[-1])
    return best

Anzahl der öffnenden und schließenden Klammern in zwei Durchläufen zählen

Idee

Der Stapel verrät dir nur, wo der aktuelle Abschnitt begonnen hat. Zwei Zähler können das ebenfalls. Gehe von links nach rechts und zähle opens und closes seit dem letzten Zurücksetzen. Wenn sie gleich sind, ist alles seit dem Zurücksetzen wohlgeformt und hat die Länge 2 × closes. Wenn closes überwiegt, hat eine ) kein Gegenstück – genau in diesem Moment hat der Stapel seine Basis verloren. Setze daher beide Zähler auf 0 zurück.

Ein Durchlauf reicht nicht aus. Eine (, die nie geschlossen wird, lässt opens dauerhaft überwiegen, und die Zähler erreichen nie wieder Gleichstand. Bei (() endet der Durchlauf von links mit 2 öffnenden und 1 schließenden Klammer und meldet nichts, obwohl () direkt darin vorkommt. Gehe also ein zweites Mal von rechts nach links und vertausche dabei die Rollen: Setze zurück, wenn opens überwiegt. Rückwärts gelesen ergibt (() zunächst eine schließende, dann eine öffnende Klammer (Gleichstand: Länge 2) und schließlich eine öffnende Klammer, die einen Neustart auslöst. Die Antwort ist der größere Wert der beiden Durchläufe.

Warum zwei Durchläufe jeden Abschnitt erfassen: Der längste Abschnitt wird von Zeichen begrenzt, die niemals zugeordnet werden können, oder von den Enden der Zeichenkette. Ist seine linke Begrenzung eine einzelne ) oder der Anfang der Zeichenkette, setzt der Durchlauf von links genau dort zurück, wo der Abschnitt beginnt, und erkennt den Gleichstand dort, wo er endet. Ist seine linke Begrenzung eine einzelne (, kann seine rechte Begrenzung keine ) sein, denn diese ) würde die einzelne ( schließen und der Abschnitt wäre länger. Die rechte Begrenzung ist also eine einzelne ( oder das Ende der Zeichenkette, und der Durchlauf von rechts erfasst den Abschnitt auf dieselbe Weise. Jeder Durchlauf liest die Zeichenkette einmal und verwendet zwei Ganzzahlen. Daher beträgt die Laufzeit O(n) und der zusätzliche Speicherbedarf O(1).

Algorithmus

Setze best auf 0 und opens und closes auf 0.
Gehe von links nach rechts und zähle jedes Zeichen. Wenn die Zähler gleich sind, aktualisiere best mit 2 × closes. Wenn closes größer ist, setze beide auf 0 zurück.
Setze beide Zähler zurück und gehe dann auf dieselbe Weise von rechts nach links, außer dass du zurücksetzt, wenn opens größer ist.
Gib best zurück.

def longestValidParentheses(s):
    best = 0

    # Left to right: more ')' than '(' ends every run that started earlier
    opens = closes = 0
    for ch in s:
        if ch == "(":
            opens += 1
        else:
            closes += 1
        if opens == closes:
            best = max(best, 2 * closes)
        elif closes > opens:
            opens = closes = 0

    # Right to left: catches the runs that an unmatched '(' hid from the first pass
    opens = closes = 0
    for ch in reversed(s):
        if ch == "(":
            opens += 1
        else:
            closes += 1
        if opens == closes:
            best = max(best, 2 * opens)
        elif opens > closes:
            opens = closes = 0

    return best

Stolperfallen und Grenzfälle

Die meisten falschen Antworten zählen die richtigen Paare an den falschen Stellen oder verlieren den Anfang eines zusammenhängenden Abschnitts.

Übereinstimmende Paare in der ganzen Zeichenfolge zählen. ())((()) hat 3 Paare, aber sie liegen nicht alle direkt nebeneinander, und die Antwort ist 4, nicht 6.
Einen zusammenhängenden Abschnitt ab der passenden ( messen. Bei ()(()) passt die letzte ) zum Index 2, was 4 ergibt und das vordere () übersieht. Miss ab dem Index, der nach dem Entfernen oben auf dem Stapel liegt.
Mit einem leeren Stapel beginnen. Für die erste ) von ()) gibt es dann nichts, woran sie gemessen werden kann, und eine nicht passende ) entfernt ein Element von einem leeren Stapel. Die Basis -1 behebt beides.
Die Zähler nur in eine Richtung laufen lassen. (() ergibt von links nach rechts 0, und ()) ergibt von rechts nach links 0; die Antwort ist für beide 2.
Die Zähler zurücksetzen, wenn sie gleich sind. Gleiche Zähler bedeuten, dass der zusammenhängende Abschnitt noch wachsen kann, wie bei ()(); setze sie nur zurück, wenn eine Seite vorne liegt.
In Lua und R beginnen Positionen bei 1, daher ist die erste Basis 0, nicht -1.

Häufige Fragen4

Wie hoch ist die Zeitkomplexität von Longest Valid Parentheses?

Sowohl die Lösung mit dem Stack als auch die Lösung mit zwei Durchläufen und Zählern liest jedes Zeichen eine konstante Anzahl von Malen und läuft daher in O(n) Zeit. Der Stack benötigt im schlimmsten Fall O(n) Speicher, beispielsweise bei einer Zeichenkette, die nur aus ( besteht, während die Zähler O(1) benötigen. Jeden Start auszuprobieren, hat eine Laufzeit von O(n²).

Warum beginnt der Stack bei -1?

Die Länge der zusammenhängenden Sequenz ist der aktuelle Index minus dem Index direkt vor der Sequenz. Bei einer Sequenz, die bei Index 0 beginnt, ist dieser frühere Index -1, also eine Position vor dem String. Wenn man zuerst -1 auf den Stack legt, ist der Stack nie leer, wenn eine passende ) die Länge misst. Wenn eine nicht passende ) den Wert entfernt, übernimmt diese ) die Rolle der neuen Basis.

Gibt es eine Lösung mit dynamischer Programmierung für „Longest Valid Parentheses“?

Ja. Sei end[i] die Länge der längsten korrekt gebildeten Teilzeichenkette, die am Index i endet; sie ist 0, wenn s[i] ( ist. Wenn s[i-1] ( ist, gilt end[i] = end[i-2] + 2. Wenn es ) ist, betrachten wir j = i - end[i-1] - 1, das Zeichen vor dem Lauf, der bei i-1 endet: Ist s[j] (, schließt es diesen Lauf ein, und end[i] = end[i-1] + 2 + end[j-1], wobei der letzte Term einen Lauf hinzufügt, der links daran anschließt. Die Antwort ist der größte Wert von end[i], bei einer Zeit- und Speicherkomplexität von O(n).

Warum reicht ein Durchlauf mit Zählern nicht aus?

Ein Durchlauf von links nach rechts wird nur zurückgesetzt, wenn ) häufiger vorkommt als (. Ein zusätzliches (, das nie geschlossen wird, hält die Zählwerte für den Rest der Zeichenkette auseinander, sodass der Durchlauf nie sieht, dass sie wieder gleich sind. Bei (() endet er mit 2 öffnenden und 1 schließenden Klammer und findet nichts. Beim Lesen von rechts nach links wird die einzelne ( so behandelt, wie der erste Durchlauf eine einzelne ) behandelt, sodass die beiden Durchläufe zusammen alle Abschnitte abdecken.

Python

def longestValidParentheses(s):
    # Schreibe hier den Code

Testfälle

Fall 1

Fall 2

Fall 3

Eingabe

s = "()(())"

Erwartet

Longest Valid Parentheses

Funktion

Einschränkungen

Beispiele

Tipps

Lösung

Erzeuge eine Teilzeichenfolge ab jeder Startposition

Stapel von Indizes mit einer Basis-Markierung

Anzahl der öffnenden und schließenden Klammern in zwei Durchläufen zählen

Stolperfallen und Grenzfälle

Häufige Fragen4

Ähnliche Aufgaben