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²) , wobei n die Länge von s , m die Anzahl der Wörter und L das längste Wort ist. Jedes Wort an jeder Position zu vergleichen, kostet O(n × m × L) . Einfache Rekursion hat eine exponentielle Laufzeit.

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

Beides. Bei der dynamischen Programmierung gibt canEnd[i] an, ob sich die ersten i Buchstaben zerlegen lassen. Als Graph betrachtet ist jeder Index ein Knoten, mit einer Kante von i nach j , wenn die Buchstaben dazwischen ein Wort bilden. Dann fragst du, ob n von 0 aus erreichbar ist. Eine Breitensuche erledigt dieselbe Arbeit wie die Tabelle.

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, die alle Wörter aus wordDict sind, und 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 Zeichenfolge, die in Wörter aufgeteilt werden soll
wordDictstring-array: die Wörter, die du so oft verwenden kannst, wie du möchtest
Gibt zurückboolean: wahr, wenn s in Wörter aus dem Wörterbuch 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 unterschiedlich.

Beispiele

Eingabe: s = "sunflowerseed"wordDict = ["sun", "flow", "flower", "seed"]
Ausgabe: true
Erklärung: Teile es in sun, flower, seed. Wenn du nach sun flow nimmst, bleibt er übrig, womit kein Wort beginnt. Daher ist das erste passende Wort nicht immer das richtige.

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

Eingabe: s = "pineappletart"wordDict = ["pine", "apple", "pineapple", "tar"]
Ausgabe: false
Erklärung: Sowohl pine + apple als auch pineapple lassen tart übrig. Nur tar passt dort hinein, wodurch ein einzelnes t übrig bleibt, also funktioniert keine Aufteilung.

Weiterführende Frage

Gib die geringste Anzahl an Wörtern zurück, die eine gültige Zerlegung verwenden kann, oder -1, wenn s nicht zerlegt 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

Sich auf jeweils ein Wort festzulegen, schlägt fehl, und alle möglichen Trennungen auszuprobieren, ist exponentiell. Ob sich der Rest von s jedoch aufteilen lässt, hängt nur davon ab, wo er beginnt. Daher gibt es nur n + 1 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

Das erste Stück muss ein Wort sein, mit dem s beginnt. Probiere jedes solche Wort aus und stelle dieselbe Frage zu den verbleibenden Buchstaben; ein leerer Rest bedeutet, dass jeder Buchstabe verwendet wurde. Wenn du jedes erste Wort und dann jedes zweite Wort ausprobierst, kannst du keinen gültigen Schnitt übersehen.

Es prüft dieselben Reste immer wieder. Bei 299 Kopien von a, gefolgt von einem b, und den Wörtern a, aa bis hin zu zehn as führen mehr als 10^89 Möglichkeiten, die a's in Blöcke aufzuteilen, bis zum b und scheitern; die Rekursion probiert sie alle aus.

Algorithmus

Schreibe canSplit(start): Können die Buchstaben von start bis zum Ende aufgeteilt werden? Wenn start der Länge von s entspricht, gib true zurück.
Für jedes Wort, das s am Index start enthält, gib true zurück, wenn canSplit(start + its length) true ist.
Gib andernfalls 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 von start ab, das n + 1 Werte annimmt. Im Beispiel mit a wird der Rest am Index 20 nach zwei Zehnerblöcken, nach zwanzig einzelnen as und auf unzählige andere Arten erreicht und ist jedes Mal false. Speichere die Antwort für jeden Start einmal und verwende sie wieder.

Das Memo muss die false-Antworten behalten. Ein true beendet die gesamte Suche sofort, daher steckt die ganze wiederholte Arbeit in Zweigen, die scheitern.

Jeder Start probiert jedes Wort aus und vergleicht bis zu L Buchstaben: O(n × m × L) Zeit, höchstens 6 × 10^6 Buchstabenprüfungen und O(n) Speicherplatz.

Algorithmus

Erstelle ein Memo mit einem Eintrag pro Index, der jeweils als noch nicht berechnet markiert ist.
Gib in canSplit(start) am Ende von s true oder die gespeicherte Antwort zurück, falls der Eintrag bereits einen Wert enthält.
Probiere andernfalls jedes Wort wie bei der einfachen Rekursion aus, speichere das Ergebnis im Eintrag – auch false – und gib es 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

Arbeite mit Präfixen. canEnd[i] gibt an, ob sich die ersten i Buchstaben zerlegen lassen; canEnd[0] ist true, da das leere Präfix keine Wörter benötigt. Die ersten end Buchstaben lassen sich genau dann zerlegen, wenn ihr letztes Teilstück von start bis end ein Wort ist und canEnd[start] true ist. Da die Werte von links nach rechts berechnet werden, ist jedes benötigte canEnd[start] bereits bekannt.

Lege die Wörter in einer Hash-Menge ab. Kein Wort ist länger als L, daher können nur die L Teilstücke, die bei end enden, passen, unabhängig davon, wie groß das Wörterbuch ist. Bei sunflowerseed ist canEnd bei 0, 3, 7, 9 und 13 wahr; die Sackgasse bei 7 schadet nicht.

An jeder der n Positionen werden höchstens L Teilstücke nachgeschlagen, für deren Erstellung und Hash-Berechnung jeweils bis zu L Schritte nötig sind: O(n × L²), höchstens 1.2 × 10^5 Schritte, plus O(m × L) für die Menge.

Algorithmus

Lege die Wörter in einer Hash-Menge ab; merke dir die maximale Länge L.
Erstelle canEnd mit n + 1 Einträgen, alle auf false gesetzt, und setze canEnd[0] auf true.
Für jedes end von 1 bis n und jede length von 1 bis min(L, end): 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 brich ab.
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

Gierig schneiden. Beim längsten Wort zuerst wird carpetal als carpet geschnitten, sodass al übrig bleibt, obwohl car + petal funktioniert; beim kürzesten Wort zuerst bleibt man bei sunflowerseed stecken.
Nur die true-Ergebnisse im Memo speichern. Die wiederholte Arbeit steckt in den false-Zweigen, daher bleibt das Beispiel mit den a's exponentiell.
Die Tabelle um einen Eintrag zu kurz machen. canEnd benötigt n + 1 Einträge für Präfixlängen von 0 bis n.
Über das Ende von s hinaus vergleichen, etwa das Wort abc mit dem Rest ab. Prüfe zuerst die Längen.
In Lua und R beginnen Zeichenkettenpositionen bei 1: Ein Stück der Länge k, das beim Buchstaben e endet, beginnt bei e-k+1.

Häufige Fragen3

Wie hoch ist die Zeitkomplexität von Word Break?

Die Bottom-up-Tabelle mit einer Hash-Menge benötigt O(m × L + n × L²), wobei n die Länge von s, m die Anzahl der Wörter und L das längste Wort ist. Jedes Wort an jeder Position zu vergleichen, kostet O(n × m × L). Einfache Rekursion hat eine exponentielle Laufzeit.

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

Beides. Bei der dynamischen Programmierung gibt canEnd[i] an, ob sich die ersten i Buchstaben zerlegen lassen. Als Graph betrachtet ist jeder Index ein Knoten, mit einer Kante von i nach j, wenn die Buchstaben dazwischen ein Wort bilden. Dann fragst du, ob n von 0 aus erreichbar ist. Eine Breitensuche erledigt dieselbe Arbeit wie die Tabelle.

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

Backtracking: Probiere an jedem Index jedes passende Wort aus, wende die Rekursion auf den Rest an und merke dir die Liste der Sätze für jeden Index. Führe zuerst die Tabelle mit Wahrheitswerten aus, damit eine Zeichenkette, die sich nicht aufteilen lässt, die Suche überspringt. Die Anzahl der Sätze kann exponentiell wachsen, daher bestimmt die Ausgabegröße die Laufzeit.

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

Test #1

Test #2

Test #3

Argumente

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

Erwartete Ausgabe

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 Fragen3

Ähnliche Aufgaben