Word Break (LeetCode 139): Dynamische Programmierung Lösungen in Python

Word Break (LeetCode 139) fragt, ob ein String in eine Folge von Wörtern zerlegt werden kann, die alle in einem Wörterbuch vorkommen. Die saubere Antwort ist dynamische Programmierung über Präfixe: Ein Präfix lässt sich bilden, wenn auf ein kürzeres, bildbares Präfix ein Wörterbuchwort folgt. Das läuft in O(n mal L), wobei L das längste Wort ist, sobald man begrenzt, wie weit man zurückblickt.

Das Problem

Gegeben sei ein String s und eine Liste von Wörtern wordDict. Gib true zurück, wenn s in ein oder mehrere Wörterbuchwörter zerlegt werden kann. Ein Wort darf beliebig oft wiederverwendet werden.

Fragen an den Interviewer: Kann das Wörterbuch Duplikate enthalten, kann es leer sein, und ist der String garantiert nicht leer? (Prüfe die Constraints auf der Problemseite.)

Brute Force

Probiere jedes erste Wort, das zum Anfang des Strings passt, und recurse dann auf dem Rest. Bei einem String wie "aaaaaaaaaab" und den Wörtern a, aa, aaa besucht die Rekursion dieselben Suffixe viele Male, die Laufzeit ist also exponentiell. Die Lösung ist, sich die Antwort für jede Startposition zu merken.

Ansatz 1: Top-down mit Memoization

Definiere can(start) als die Frage, ob der ab start beginnende Suffix zerlegt werden kann. Cache das Ergebnis.

from functools import lru_cache

def word_break_memo(s, word_dict):
    words = set(word_dict)

    @lru_cache(maxsize=None)
    def can(start):
        if start == len(s):
            return True
        for end in range(start + 1, len(s) + 1):
            if s[start:end] in words and can(end):
                return True
        return False

    return can(0)

Jede der n Startpositionen wird einmal gelöst, und jede probiert bis zu n Endpositionen aus, mit einem Slice und einem Set-Lookup. Das sind O(n zum Quadrat) Lookups, bzw. O(n hoch 3) Zeichenarbeit, wenn man die Kosten für das Erzeugen jedes Slices mitzählt. Der Speicherbedarf ist O(n) für den Cache und die Rekursion.

Ansatz 2: Bottom-up dynamische Programmierung

Sei dp[i] true, wenn die ersten i Zeichen zerlegt werden können. dp[0] ist true, da das leere Präfix keine Wörter braucht. Suche für jede Endposition einen Start, an dem dp[start] true ist und s[start:end] ein Wort ist.

def word_break(s, word_dict):
    words = set(word_dict)
    max_len = max((len(w) for w in words), default=0)
    dp = [False] * (len(s) + 1)
    dp[0] = True
    for end in range(1, len(s) + 1):
        for start in range(max(0, end - max_len), end):
            if dp[start] and s[start:end] in words:
                dp[end] = True
                break
    return dp[len(s)]

start auf die letzten max_len Positionen zu begrenzen, ist wichtig. Ein Wörterbuchwort kann nicht länger sein als das längste Wort, also bringt es nichts, längere Slices zu prüfen. Dadurch wird die innere Schleife zu höchstens L Schritten und das Ganze zu O(n mal L) Lookups.

Trace

Für s = "leetcode" mit ["leet","code"]: dp[0] ist true. dp[4] wird true, weil dp[0] true ist und "leet" ein Wort ist. dp[8] wird true, weil dp[4] true ist und "code" ein Wort ist. Die Antwort ist dp[8], also true.

Häufige Fehler

• Vergessen, dass Wörter wiederverwendet werden können.
• True zurückgeben, sobald irgendein Präfix ein Wort ist. Der ganze String muss abgedeckt sein.
• Jeden Slice ohne die max_len-Begrenzung erzeugen, was korrekt, aber bei langen Strings langsam ist.
• Das Wörterbuch zu spät oder gar nicht in ein Set umwandeln, sodass jeder Lookup eine Liste durchsucht.

Edge Cases zum Testen

Wie man es im Interview erklärt

1. Nenne die Brute-Force-Lösung und warum sie Arbeit wiederholt.
2. Formuliere das Teilproblem: Kann das Präfix der Länge i gebildet werden?
3. Schreibe die Rekurrenz in Worten auf und dann die Bottom-up-Version als Code.
4. Erwähne die max_len-Begrenzung und gib die Komplexität an.
5. Biete die memoisierte Version an, falls der Interviewer Rekursion bevorzugt.

Ich habe beide Versionen oben gegen eine Brute-Force-Suche mit 20.000 zufälligen kleinen Eingaben getestet, plus die drei Beispiele in der Tabelle, bevor ich das veröffentlicht habe. So ein schneller Zufallstest ist eine gute Angewohnheit beim Üben.

Verwandte Übungen

Sieh dir unseren Big-O-Cheat-Sheet für die Komplexitätsbegriffe an, die LeetCode Blind 75 Liste für das, was du als Nächstes üben solltest, und den Coding-Interview-Assistenten-Leitfaden für die Übung.

Sprich deinen Ansatz laut durch, während du codest. Ein Transkript zeigt, ob du die entscheidende Beobachtung genannt hast, bevor du geschrieben hast. Befolge bei jeder Live-Assessment die Regeln des Arbeitgebers zu KI-Tools.