Word Ladder (LeetCode 127): BFS mit Wildcard-Mustern in Python

Word Ladder (LeetCode 127) verlangt die Länge der kürzesten Kette von einem Wort zu einem anderen, wobei jeweils ein Buchstabe geändert wird und jeder Zwischenschritt in einer gegebenen Liste stehen muss. Kürzester Pfad mit gleich langen Schritten bedeutet Breitensuche. Der Trick, der das Ganze schnell macht, ist, Wörter nach Wildcard-Mustern wie h*t zu gruppieren, sodass du nicht jedes Wortpaar vergleichen musst.

Das Problem

Gegeben sind beginWord, endWord und eine Liste von Wörtern. Gib die Anzahl der Wörter in der kürzesten Transformationssequenz von beginWord zu endWord zurück, wobei beide Enden mitzählen. Jeder Schritt ändert genau einen Buchstaben, und jedes Wort, zu dem du wechselst, muss in der Liste stehen. Gib 0 zurück, wenn es keine solche Sequenz gibt.

Warum Breitensuche

Betrachte jedes Wort als Knoten, mit einer Kante zwischen zwei Wörtern, die sich in einem Buchstaben unterscheiden. Jede Kante kostet einen Schritt, also ist die kürzeste Sequenz der kürzeste Pfad in einem ungewichteten Graphen, und die Breitensuche findet ihn, sobald sie das Endwort zum ersten Mal erreicht.

Kanten per Brute Force aufbauen

Jedes Wortpaar zu vergleichen, um festzustellen, ob es sich in einem Buchstaben unterscheidet, kostet O(N zum Quadrat mal L) für N Wörter der Länge L. Bei Tausenden von Wörtern ist das langsam. Besser: Nachbarn aus Mustern erzeugen.

Ansatz: Wildcard-Muster

Ersetze nacheinander jeden Buchstaben durch *. Aus hot wird *ot, h*t und ho*. Zwei Wörter sind genau dann Nachbarn, wenn sie sich ein Muster teilen. Baue eine Map von Muster zu den passenden Wörtern und führe damit die Suche aus.

from collections import deque, defaultdict

def ladder_length(begin_word, end_word, word_list):
    words = set(word_list)
    if end_word not in words:
        return 0
    patterns = defaultdict(list)
    for w in words | {begin_word}:
        for i in range(len(w)):
            patterns[w[:i] + "*" + w[i + 1:]].append(w)
    queue = deque([(begin_word, 1)])
    seen = {begin_word}
    while queue:
        word, steps = queue.popleft()
        if word == end_word:
            return steps
        for i in range(len(word)):
            key = word[:i] + "*" + word[i + 1:]
            for nxt in patterns[key]:
                if nxt not in seen:
                    seen.add(nxt)
                    queue.append((nxt, steps + 1))
            patterns[key] = []
    return 0

Zwei Details sind wichtig. Das Startwort wird zur Muster-Map hinzugefügt, auch wenn es nicht in der Liste steht, da du von ihm aus startest. Und nachdem die Wörter eines Musters besucht wurden, leert patterns[key] = [] es, damit dieselbe Gruppe nicht von jedem anderen Wort, das sich das Muster teilt, erneut durchsucht wird. So bleibt der Gesamtaufwand linear in der Anzahl der Muster.

Komplexität

Das Aufbauen der Muster dauert O(N mal L), und jeder Muster-String kostet O(L) zum Erzeugen, also insgesamt etwa O(N mal L zum Quadrat). Die Suche berührt jedes Wort einmal und jede Mustergruppe einmal, mit derselben Schranke. Der Speicherbedarf ist O(N mal L zum Quadrat) für die Muster-Map, da jedes Wort unter L Schlüsseln der Länge L gespeichert wird.

Schneller: bidirektionale Suche

Starte eine Suche vom Startwort und eine vom Endwort und erweitere immer die kleinere Frontier. Sie treffen sich in der Mitte, sodass jede Seite nur die halbe Tiefe durchsucht. Es lohnt sich, das zu erwähnen, wenn der Interviewer fragt, wie man es beschleunigen kann, und es ist mehr Code, als die meisten Interviews von dir erwarten.

Häufige Fehler

• Die Anzahl der Änderungen statt der Anzahl der Wörter zurückgeben. Die Sequenz enthält beginWord, das Beispiel ergibt also 5, nicht 4.
• Nicht prüfen, ob endWord in der Liste steht, bevor du suchst.
• Nachbarn per paarweisem Vergleich aufbauen und ein Timeout kassieren.
• Die Suche Wörter erneut besuchen lassen, was zu Schleifen führt oder sie verlangsamt.
• DFS verwenden, das einen Pfad findet, aber nicht den kürzesten.

Edge Cases zum Testen

Wie du es im Interview erklärst

1. Formuliere es als Graph um und sage, warum die Breitensuche den kürzesten Pfad findet.
2. Sage, dass der paarweise Vergleich zu langsam ist, und führe Wildcard-Muster ein.
3. Schreibe die Muster-Map, die Queue und das Visited-Set.
4. Sage, dass du Wörter zählst, nicht Änderungen, und zeige das erste Beispiel.
5. Gib die Komplexität an und erwähne die bidirektionale Suche.

Ich habe den obigen Code gegen eine einfache paarweise Breitensuche mit 20.000 zufälligen kleinen Wortlisten getestet, plus die beiden Beispiele in der Tabelle, bevor ich ihn veröffentlicht habe. So eine schnelle Zufallsprüfung ist eine gute Angewohnheit beim Üben.

Verwandte Übung

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 Leitfaden zum Coding-Interview-Assistenten für die Übung.

Sprich deinen Ansatz laut durch, während du codest. Ein Transkript zeigt, ob du die entscheidende Beobachtung vor dem Schreiben genannt hast. Befolge die Regeln des Arbeitgebers zu KI-Tools in jeder Live-Prüfung.