Word Break

Q: Wie hoch ist die Zeitkomplexität von Word Break?

Die Bottom-up-Tabelle mit einer Hash-Menge benötigt O(m × L + n × L²) Zeit, wobei n die Länge von s ist, m die Anzahl der Wörter und L das längste Wort. Beim Erstellen der Menge wird jedes Wort einmal gelesen, und an jeder der n Positionen werden höchstens L Teilzeichenfolgen mit bis zu L Buchstaben nachgeschlagen. Wenn du stattdessen jedes Wort an jeder Position vergleichst, beträgt die Laufzeit O(n × m × L) . Einfache Rekursion ohne Memoisierung hat exponentielle Laufzeit.

MittelDynamische Programmierung Hashing

+10

Du erhältst eine Zeichenfolge s und eine Liste von Wörtern wordDict. Gib true zurück, wenn du s in Teile zerlegen kannst, sodass jeder Teil ein Wort aus wordDict ist, andernfalls false.

Die Teile behalten ihre Reihenfolge bei und verwenden zusammen jeden Buchstaben von s genau einmal. Ein Wort kann beliebig oft verwendet werden, und du musst nicht jedes Wort verwenden.

Funktion

wordBreak(s: string, wordDict: string-array) → boolean

sstring: die Zeichenkette, die in Wörter zerlegt werden soll
wordDictstring-array: die Wörter, die du verwenden darfst, so oft du möchtest
Gibt zurückboolean: wahr, wenn s in Wörterbuchwörter zerlegt werden kann, andernfalls falsch

Einschränkungen

1 ≤ s.length ≤ 300
1 ≤ wordDict.length ≤ 1000
1 ≤ wordDict[i].length ≤ 20
s und jedes Wort enthält nur englische Kleinbuchstaben.
Die Wörter in wordDict sind alle verschieden.

Beispiele

Eingabe: s = "sunflowerseed"wordDict = ["sun", "flow", "flower", "seed"]
Ausgabe: true
Erklärung: Teile es in sun, flower, seed auf. Nimmt man flow nach sun, führt das zu nichts, da kein Wort mit dem übrig gebliebenen er beginnt. Das erste passende Wort ist also nicht immer das richtige.

Eingabe: s = "bananaban"wordDict = ["ban", "ana"]
Ausgabe: true
Erklärung: ban + ana + ban deckt den String ab und verwendet ban zweimal, was erlaubt ist.

Eingabe: s = "pineappletart"wordDict = ["pine", "apple", "pineapple", "tar"]
Ausgabe: false
Erklärung: Die Zeichenfolge beginnt mit pine + apple oder mit pineapple, und bei beiden bleibt tart übrig. Das einzige Wort, das dort passt, ist tar, wodurch ein einzelnes t übrig bleibt, also funktioniert kein Schnitt.

+21 versteckte Tests beim Einreichen

Weiterführende Frage

Gib die geringstmögliche Anzahl an Wörtern zurück, die ein gültiger Schnitt verwenden kann, oder -1, wenn s nicht zerschnitten werden kann. Was ändert sich in der Tabelle, und ändert sich die Laufzeit?

Tipps

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

0 von 3 geöffnet

Lösung

Gieriges Aufteilen scheitert in beide Richtungen: Nimmt man zuerst das kürzeste Wort, wird sunflowerseed in sun + flow aufgeteilt, und nimmt man zuerst das längste, wird carpetal als carpet aufgeteilt und al bleibt übrig. Du musst also die Möglichkeiten ausprobieren, und ein String lässt sich auf exponentiell viele Arten aufteilen. Der entscheidende Punkt ist, dass es nur davon abhängt, wo der Rest des Strings beginnt, ob sich dieser Rest aufteilen lässt. Deshalb gibt es nur n + 1 verschiedene Fragen. Im Folgenden ist n die Länge von s, m die Anzahl der Wörter und L die Länge des längsten Wortes.

Probiere jedes Wort an jeder Position aus

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

Idee

Lies s von links. Was auch immer das erste Stück ist, es muss ein Wort sein, mit dem s beginnt. Probiere jedes solche Wort aus und stelle für jedes dieselbe Frage zu den verbleibenden Buchstaben. Wenn irgendein Wort zu einer vollständigen Zerlegung führt, lautet die Antwort true. Wenn keines dazu führt, lautet sie false. Wenn nichts mehr übrig ist, hast du jeden Buchstaben zerlegt, also gilt das als Erfolg.

Das probiert jedes mögliche erste Wort aus, dann jedes mögliche zweite Wort und so weiter. Daher kann keine gültige Zerlegung übersehen werden, und jedes zurückgegebene true entspricht einer tatsächlichen Zerlegung.

Es ist langsam, weil dieselben Reste immer wieder geprüft werden. Nimm 299 Kopien von a, gefolgt von einem b, mit den Wörtern a, aa und so weiter bis zu zehn a. Jede Möglichkeit, die a's in Blöcke mit höchstens zehn Buchstaben zu zerlegen, erreicht das b und scheitert dort, und es gibt mehr als 10^89 solcher Möglichkeiten. Die Rekursion muss sie alle ausprobieren, bevor sie false zurückgeben kann.

Algorithmus

Schreibe eine Hilfsfunktion canSplit(start), die angibt, ob sich die Buchstaben vom Index start bis zum Ende in Wörter aufteilen lassen.
Wenn start der Länge von s entspricht, gib true zurück.
Prüfe für jedes Wort, ob s es ab Index start enthält.
Wenn ja und canSplit(start + length of the word) true ist, gib true zurück.
Wenn kein Wort passt, gib false zurück. Die Antwort ist canSplit(0).

def wordBreak(s, wordDict):
    def can_split(start):
        # Can s[start:] be cut into dictionary words?
        if start == len(s):
            return True  # nothing left to cut
        for word in wordDict:
            if s.startswith(word, start) and can_split(start + len(word)):
                return True
        return False

    return can_split(0)

Rekursion mit Memoisierung

Idee

Die Antwort für einen Rest hängt nur davon ab, wo er beginnt, und start nimmt nur n + 1 Werte an. Im Beispiel mit den a's wird der Rest, der bei Index 20 beginnt, nach zwei Blöcken mit je zehn, nach zwanzig einzelnen as und auf unzählige andere Arten erreicht, und die Antwort lautet jedes Mal false. Speichere die Antwort für jeden Start beim ersten Berechnen und lies sie danach wieder aus.

Ein Memo-Slot benötigt drei Zustände: noch nicht berechnet, true und false. Die Antworten false sind entscheidend. Ein true beendet die gesamte Suche sofort, daher wiederholt die einfache Rekursion ihre Arbeit ausschließlich in Zweigen, die fehlschlagen.

Jeder Start wird einmal berechnet und probiert jedes Wort aus, wobei bis zu L Buchstaben verglichen werden. Die Laufzeit beträgt also O(n × m × L): hier höchstens 300 × 1000 × 20 = 6 × 10^6 Buchstabenvergleiche. Das Memo und der Aufrufstapel benötigen O(n) Speicherplatz, und die Aufrufe sind höchstens 300 Ebenen tief verschachtelt.

Algorithmus

Lege eine Merktabelle mit einem Eintrag pro Index an, die jeweils als noch nicht berechnet markiert sind.
Gib in canSplit(start) am Ende des Strings true zurück und gib die gespeicherte Antwort zurück, wenn der Eintrag für start einen Wert enthält.
Andernfalls probiere wie bei der einfachen Rekursion jedes Wort aus, das bei start beginnt, und höre beim ersten auf, dessen Rest sich aufteilen lässt.
Speichere das Ergebnis im Eintrag, auch wenn es false ist, und gib es zurück.
Gib canSplit(0) zurück.

def wordBreak(s, wordDict):
    memo = [None] * len(s)  # memo[start]: answer for s[start:], None until worked out

    def can_split(start):
        if start == len(s):
            return True
        if memo[start] is not None:
            return memo[start]
        result = False
        for word in wordDict:
            if s.startswith(word, start) and can_split(start + len(word)):
                result = True
                break
        memo[start] = result
        return result

    return can_split(0)

Bottom-up über Präfixe mit einer Hash-Menge

Idee

Dreh den Ansatz um und arbeite mit Präfixen. Lass canEnd[i] angeben, ob sich die ersten i Buchstaben in Wörter zerlegen lassen. Das leere Präfix benötigt keine Wörter, also ist canEnd[0] true. Die ersten end Buchstaben lassen sich genau dann zerlegen, wenn ihr letztes Stück, die Buchstaben von start bis end, ein Wort ist und die Buchstaben davor zerlegt werden können, das heißt, canEnd[start] ist true. Fülle die Tabelle von links nach rechts aus, dann ist jedes benötigte canEnd[start] bereits bekannt.

Statt an jeder Position alle m Wörter zu vergleichen, speichere die Wörter in einer Hash-Menge und suche darin nach möglichen letzten Stücken. Kein Wort ist länger als L, daher können nur die L Stücke, die bei end enden, übereinstimmen. Bei sunflowerseed wird canEnd bei 0, bei 3 (sun), bei 7 (flow), bei 9 (flower) und bei 13 (seed nach Position 9) zu true, also lautet die Antwort true. Von Position 7 aus geht es nicht weiter, weil kein Wort mit er beginnt; die Tabelle berücksichtigt das nicht.

Es gibt n Positionen, an jeder werden höchstens L Stücke nachgeschlagen, und das Erstellen und Hashen eines Stücks kostet bis zu L Schritte. Das ergibt O(n × L²), höchstens 300 × 20 × 20 = 1.2 × 10^5 Buchstabenschritte, unabhängig davon, wie groß das Wörterbuch ist. Beim Erstellen der Menge wird jedes Wort einmal gelesen, also O(m × L); insgesamt ergibt sich damit O(m × L + n × L²). Die Menge speichert die Wörter, also O(m × L) Buchstaben, und die Tabelle speichert n + 1 Wahrheitswerte. Es gibt keine Rekursion.

Algorithmus

Füge jedes Wort in eine Hash-Menge ein und notiere die Länge L des längsten Wortes.
Erstelle canEnd mit n + 1 Einträgen, die alle false sind, und setze canEnd[0] auf true.
Gehe für jedes end von 1 bis n jede length von 1 bis min(L, end) durch.
Wenn canEnd[end-length] true ist und das Teilstück dieser Länge, das bei end endet, in der Menge enthalten ist, setze canEnd[end] auf true und höre auf, weitere Längen auszuprobieren.
Gib canEnd[n] zurück.

def wordBreak(s, wordDict):
    words = set(wordDict)
    longest = max(len(word) for word in wordDict)
    n = len(s)
    # can_end[i]: the first i letters split into dictionary words
    can_end = [False] * (n + 1)
    can_end[0] = True  # the empty prefix needs no words
    for end in range(1, n + 1):
        # The last word is s[end-length:end], and no word is longer than longest.
        for length in range(1, min(longest, end) + 1):
            if can_end[end - length] and s[end - length:end] in words:
                can_end[end] = True
                break
    return can_end[n]

Stolperfallen und Grenzfälle

Die meisten falschen Antworten entstehen dadurch, dass man sich zu früh auf eine Aufteilung festlegt oder eine Suche durchführt, die sich ihre Fehlschläge nicht merkt.

Gierig aufteilen. Nimmt man zuerst das längste Wort, wird carpetal in carpet aufgeteilt und al bleibt übrig, obwohl car + petal funktioniert. Nimmt man zuerst das kürzeste Wort, scheitert man bei sunflowerseed.
Nur prüfen, ob jeder Buchstabe von s in irgendeinem Wort vorkommt. Bei den Wörtern aaaa und aa hat jedes Teilstück eine gerade Länge, daher lässt sich aaaaaaa mit sieben Buchstaben nicht aufteilen.
Nur die true-Ergebnisse im Memo speichern. Bei true endet die Suche ohnehin. Die wiederholte Arbeit steckt in den false-Zweigen, daher bleibt eine Memoisierung ohne sie exponentiell.
Die Tabelle um einen Eintrag zu kurz anlegen. canEnd[i] bezieht sich auf die ersten i Buchstaben, und sowohl 0 als auch n sind gültig, daher braucht sie n + 1 Einträge.
Über das Ende von s hinaus vergleichen, wenn ein Wort länger ist als der verbleibende Teil, etwa das Wort abc mit ab. Prüfe die Längen, bevor du die Buchstaben vergleichst.
In Lua und R beginnen Zeichenfolgenpositionen bei 1: Ein Teilstück der Länge k, das beim Buchstaben e endet, beginnt beim Buchstaben e-k+1.

Häufige Fragen4

Wie hoch ist die Zeitkomplexität von Word Break?

Die Bottom-up-Tabelle mit einer Hash-Menge benötigt O(m × L + n × L²) Zeit, wobei n die Länge von s ist, m die Anzahl der Wörter und L das längste Wort. Beim Erstellen der Menge wird jedes Wort einmal gelesen, und an jeder der n Positionen werden höchstens L Teilzeichenfolgen mit bis zu L Buchstaben nachgeschlagen. Wenn du stattdessen jedes Wort an jeder Position vergleichst, beträgt die Laufzeit O(n × m × L). Einfache Rekursion ohne Memoisierung hat exponentielle Laufzeit.

Warum scheitert ein gieriger Ansatz bei Word Break?

Eine gierige Regel legt sich auf ein Wort fest und überdenkt es nie wieder. Die längste Übereinstimmung zuerst zerlegt carpetal in carpet und al, während car + petal funktioniert. Die kürzeste Übereinstimmung zuerst zerlegt sunflowerseed in sun + flow und bleibt bei erseed stecken. Dynamische Programmierung behält jede Position bei, die durch irgendeine Zerlegung erreicht werden kann, und verliert so nie die richtige.

Ist Word Break ein Problem der dynamischen Programmierung oder ein Graphproblem?

Beide Sichtweisen funktionieren. Beim dynamischen Programmieren gibt canEnd[i] an, ob die ersten i Buchstaben aufgeteilt werden können, und wird aus kleineren Präfixen aufgebaut. Als Graph ist jeder Index ein Knoten, mit einer Kante von i nach j, wenn die Buchstaben von i bis j ein Wort bilden, und du fragst, ob Knoten n von Knoten 0 aus erreichbar ist. Eine Breitensuche mit einer Menge besuchter Knoten erledigt dieselbe Arbeit wie die Tabelle.

Wie listest du jeden Satz auf, anstatt true oder false zurückzugeben?

Verwende Backtracking: Probiere an jedem Index jedes passende Wort aus und rufe die Funktion rekursiv mit dem Rest auf, während du den Satz schrittweise aufbaust. Speichere die Satzliste für jeden Index, damit ein Rest nur einmal gelöst wird. Führe zuerst die Tabelle mit Wahrheitswerten aus, damit Zeichenfolgen, die sich nicht aufteilen lassen, die Suche überspringen. Die Anzahl der Sätze kann exponentiell wachsen, daher bestimmt die Größe der Ausgabe die Laufzeit.

Python

def wordBreak(s, wordDict):
    # Schreibe hier den Code

Testfälle

Fall 1

Fall 2

Fall 3

Eingabe

s = "sunflowerseed"
wordDict = ["sun", "flow", "flower", "seed"]

Erwartet

true

Word Break

Funktion

Einschränkungen

Beispiele

Tipps

Lösung

Probiere jedes Wort an jeder Position aus

Rekursion mit Memoisierung

Bottom-up über Präfixe mit einer Hash-Menge

Stolperfallen und Grenzfälle

Häufige Fragen4

Ähnliche Aufgaben