Word Ladder

Q: Kann bidirektionale BFS Word Ladder schneller machen?

Ja. Suche gleichzeitig von beginWord und endWord aus, erweitere dabei immer die kleinere Seite um eine Ebene und halte an, wenn ein neues Wort bereits von der anderen Seite erreicht wurde. Die Wortleiter hat dann ein Wort mehr als die zusammen auf beiden Seiten vorgenommenen Änderungen. Wenn jedes Wort etwa b Nachbarn hat und die Wortleiter d Änderungen umfasst, kann eine Suche etwa b^d Wörter erreichen, während zwei Suchen, die sich in der Mitte treffen, etwa 2 × b^(d/2) Wörter erreichen.

SchwerGraphen Warteschlange

+10

Du erhältst zwei Wörter, beginWord und endWord, sowie eine Wortliste wordList. Eine Leiter ist eine Folge von Wörtern, die mit beginWord beginnt, mit endWord endet und bei der sich jedes Wort vom nächsten genau in einem Buchstaben unterscheidet. Jedes Wort nach beginWord muss aus wordList stammen.

Gib die Anzahl der Wörter in der kürzesten Leiter zurück, einschließlich beider Enden, oder 0, wenn keine Leiter existiert. Zum Beispiel ist cold, cord, card eine Leiter aus 3 Wörtern. beginWord muss nicht in wordList enthalten sein, aber endWord muss es.

Funktion

ladderLength(beginWord: string, endWord: string, wordList: string-array) → integer

beginWordstring: das erste Wort der Leiter
endWordstring: das Wort, das die Leiter erreichen muss
wordListstring-array: die Wörter, aus denen jeder spätere Schritt stammen muss
Gibt zurückinteger: die Anzahl der Wörter in der kürzesten Wortleiter oder 0, wenn es keine gibt

Einschränkungen

1 ≤ beginWord.length ≤ 10
endWord und jedes Wort in wordList haben dieselbe Länge wie beginWord.
1 ≤ wordList.length ≤ 5000
Alle Wörter enthalten ausschließlich englische Kleinbuchstaben.
beginWord != endWord
Die Wörter in wordList sind alle verschieden. beginWord kann eines davon sein oder auch nicht.

Beispiele

Eingabe: beginWord = "lead"endWord = "gold"wordList = ["load", "goad", "gold", "lend", "lewd", "bold"]
Ausgabe: 4
Erklärung: lead und gold unterscheiden sich in drei Buchstaben, daher hat keine Wortleiter weniger als 4 Wörter, und lead, load, goad, gold hat genau 4. Auch lend und lewd unterscheiden sich von lead in einem Buchstaben, aber keines von beiden führt irgendwohin, wo man noch nicht war, und bold ist nur von gold selbst aus erreichbar.

Eingabe: beginWord = "cat"endWord = "dog"wordList = ["cot", "cog", "dot", "dig"]
Ausgabe: 0
Erklärung: cat, cot, cog kommt bis auf einen Buchstaben an dog heran, aber dog steht nicht in der Liste, daher kann dort keine Leiter enden.

Eingabe: beginWord = "ab"endWord = "cd"wordList = ["ab", "cb", "cd", "ad"]
Ausgabe: 3
Erklärung: ab, ad, cd und ab, cb, cd umfassen beide 3 Wörter. ab ist ebenfalls in der Liste, aber der Start wird so oder so nur einmal gezählt.

+14 versteckte Tests beim Einreichen

Weiterführende Frage

Kannst du eine kürzeste Wortleiter selbst zurückgeben, also die Wörter in der Reihenfolge, und nicht nur ihre Länge?

Tipps

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

0 von 3 geöffnet

Lösung

Betrachte die Wörter als Knoten eines Graphen, mit einer Kante zwischen zwei Wörtern, die sich in einem Buchstaben unterscheiden. Eine Leiter ist dann ein Pfad von beginWord zu endWord, und jede Kante hat die gleichen Kosten, daher ist die kürzeste Leiter der Pfad mit den wenigsten Kanten. Die Breitensuche findet genau diesen Pfad. Schwierig ist, die Kanten schnell zu finden: Jedes Paar von 5.000 Wörtern zu vergleichen, ergibt 25 Millionen Vergleiche, deshalb sucht die beste Lösung Nachbarn stattdessen über Platzhaltermuster. Unten ist n die Anzahl der Wörter und L ihre Länge.

Probiere jede Leiter mit Tiefensuche aus

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

Idee

Beginne bei beginWord. Probiere vom aktuellen Wort aus jedes unbenutzte Wort aus, das sich um einen Buchstaben unterscheidet, und gehe von dort aus weiter. Wenn du endWord erreichst, notiere die Länge der Wortleiter, falls sie bisher die kürzeste ist. Markiere die Wörter auf dem aktuellen Pfad als benutzt, damit eine Wortleiter nicht zu sich selbst zurückführt, und gib jedes Wort wieder frei, wenn du zurückgehst, damit andere Wortleitern es verwenden können. Sobald du eine Wortleiter mit best Wörtern hast, höre auf, Pfade zu verlängern, die bereits best-1 Wörter haben: Sie können nicht kürzer abgeschlossen werden.

Das ist korrekt, weil alle Wortleitern ausprobiert werden, die kein Wort wiederholen, und eine kürzeste Wortleiter nie ein Wort wiederholt: Wenn ein Wort zweimal vorkäme, würde das Entfernen des Abschnitts zwischen den beiden Vorkommen eine kürzere Wortleiter ergeben.

Das ist langsam, weil die Anzahl der Wortleitern explosionsartig wächst. Nimm 26 Wörter, die sich nur im ersten Buchstaben unterscheiden, aaa, baa bis zaa: Jedes Paar unterscheidet sich um einen Buchstaben, sodass die Suche sie in beliebiger Reihenfolge durchlaufen kann, bevor sie fortfährt, und 26 Wörter lassen sich auf etwa 4 × 10^26 Arten anordnen. Die Beschneidung hilft erst, wenn eine Wortleiter gefunden wurde. Wenn endWord überhaupt nicht erreicht werden kann, wird nie etwas abgeschnitten, und eine Liste mit 34 Wörtern übersteigt bereits das, was die Suche bewältigen kann. Die Rekursion geht außerdem so tief wie die Wortleiter, die Tausende von Wörtern lang sein kann.

Algorithmus

Markiere beginWord als verwendet, falls es in der Liste steht, und setze best auf 0.
Schreibe search(word, length). Wenn word gleich endWord ist, übernimm length, wenn es besser als best ist, und kehre zurück.
Wenn best nicht 0 ist und length + 1 ≥ best, kehre zurück: Dieser Pfad kann nicht gewinnen.
Für jedes ungenutzte Wort, das sich um einen Buchstaben von word unterscheidet, markiere es als verwendet, rufe search(next, length + 1) auf und markiere es anschließend wieder als ungenutzt.
Rufe search(beginWord, 1) auf und gib best zurück, das 0 bleibt, wenn keine Wortleiter existiert.

def ladderLength(beginWord, endWord, wordList):
    def one_letter_apart(a, b):
        differences = 0
        for x, y in zip(a, b):
            if x != y:
                differences += 1
                if differences > 1:
                    return False
        return differences == 1

    best = 0  # words in the shortest sequence found so far, 0 while there is none
    used = [word == beginWord for word in wordList]  # words on the current path

    def search(word, length):
        nonlocal best
        if word == endWord:
            if best == 0 or length < best:
                best = length
            return
        if best != 0 and length + 1 >= best:
            return  # any longer path cannot beat the best one
        for i, candidate in enumerate(wordList):
            if not used[i] and one_letter_apart(word, candidate):
                used[i] = True
                search(candidate, length + 1)
                used[i] = False  # free the word for other paths

    search(beginWord, 1)
    return best

Breitensuche, jeden Paarvergleich

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

Idee

Die Breitensuche durchläuft die Wörter in der Reihenfolge ihrer Entfernung. Zuerst kommt beginWord, eine Leiter mit 1 Wort. Dann jedes Wort, das sich um einen Buchstaben davon unterscheidet: Leitern mit 2 Wörtern. Danach jedes neue Wort, das sich um einen Buchstaben von diesen unterscheidet: Leitern mit 3 Wörtern und so weiter. Eine Warteschlange hält diese Reihenfolge aufrecht: Wörter verlassen sie in der Reihenfolge, in der sie hinzugefügt wurden. Daher verlassen alle Wörter mit Entfernung d die Warteschlange, bevor irgendein Wort mit Entfernung d + 1 sie verlässt.

Diese Reihenfolge ist der Grund, warum die erste von der Breitensuche gefundene Leiter eine kürzeste ist. Wenn ein Wort erstmals mit Entfernung d erreicht wird, wurden bereits alle Wörter mit geringerer Entfernung durchsucht. Gäbe es also eine kürzere Leiter zu diesem Wort, hätte die Suche es früher erreicht. Dasselbe Argument zeigt, warum es sicher ist, ein Wort in dem Moment als besucht zu markieren, in dem es der Warteschlange hinzugefügt wird: Seine Entfernung steht fest, und ein späteres erneutes Erreichen kann nur über einen längeren Weg erfolgen. Jedes Wort wird also genau einmal der Warteschlange hinzugefügt, und sobald endWord als Nachbar auftaucht, ist seine Entfernung die Antwort.

Diese Version findet die Nachbarn eines Wortes, indem sie es mit jedem Wort in der Liste vergleicht, Buchstabe für Buchstabe, und beim zweiten Unterschied abbricht. Bei bis zu n Wörtern, die die Warteschlange verlassen, kostet das jeweils n Vergleiche von bis zu L Buchstaben, insgesamt also O(n² × L). Bei 5.000 Wörtern und einer Suche, die die meisten davon besucht, sind das bis zu 25 Millionen Wortvergleiche. Eine kompilierte Sprache bewältigt das schnell, aber Python benötigt beim größten Test mehrere Sekunden.

Algorithmus

Wenn endWord nicht in wordList enthalten ist, gib 0 zurück.
Füge beginWord mit der Länge 1 in eine Warteschlange ein. Markiere es als besucht, wenn es in der Liste enthalten ist.
Nimm das nächste Wort und seine Länge aus der Warteschlange.
Vergleiche es mit jedem unbesuchten Wort in der Liste. Für jedes Wort, das sich in genau einem Buchstaben unterscheidet: Wenn es endWord ist, gib length + 1 zurück; andernfalls markiere es als besucht und füge es mit der Länge length + 1 hinzu.
Wenn die Warteschlange leer ist, ist endWord nicht erreichbar: Gib 0 zurück.

from collections import deque


def ladderLength(beginWord, endWord, wordList):
    def one_letter_apart(a, b):
        differences = 0
        for x, y in zip(a, b):
            if x != y:
                differences += 1
                if differences > 1:
                    return False
        return differences == 1

    if endWord not in wordList:
        return 0
    visited = [word == beginWord for word in wordList]
    queue = deque([(beginWord, 1)])  # (word, words in the sequence up to it)
    while queue:
        word, length = queue.popleft()
        # Compare against every word to find the neighbours.
        for i, candidate in enumerate(wordList):
            if not visited[i] and one_letter_apart(word, candidate):
                if candidate == endWord:
                    return length + 1
                visited[i] = True
                queue.append((candidate, length + 1))
    return 0

Breitensuche mit Platzhalter-Buckets

Idee

Behalte die Breitensuche bei und sorge dafür, dass sich Nachbarn günstig finden lassen. Zwei Wörter unterscheiden sich genau dann um einen Buchstaben, wenn sie gleich werden, sobald man an derselben Stelle bei beiden einen Buchstaben ausblendet: hot und hit werden beide zu h*t. Erzeuge also für jedes Wort L Muster, eines für jede ausgeblendete Position, und füge das Wort für jedes Muster einem Bucket hinzu. Die Nachbarn eines Wortes sind die übrigen Wörter in seinen L Buckets. Sie lassen sich mit L Hash-Lookups finden, statt die gesamte Liste zu durchlaufen.

Hier ist die Suche beim ersten Beispiel. lead hat die Muster *ead, l*ad, le*d und lea*. Der Bucket l*ad enthält load, und le*d enthält lend und lewd, also sind diese drei Wörter auf Ebene 2. Von load aus ergibt der Bucket *oad auf Ebene 3 goad, und von goad aus ergibt go*d auf Ebene 4 gold.

Eine weitere Einsparung: Sobald der Bucket eines Wortes durchsucht wurde, wurde jedes Wort darin erreicht, also leere ihn. Spätere Wörter, die dasselbe Muster haben, würden dort ohnehin nichts Neues finden. Im Test, bei dem aaa, baa bis hin zu zaa das Muster *aa gemeinsam haben, wird dieser Bucket mit 26 Wörtern nur einmal statt 26-mal durchsucht. So liest die Suche jeden der n × L Bucket-Einträge höchstens einmal.

Das Erstellen der Muster benötigt n × L Zeichenketten aus jeweils L Buchstaben, Zeit und Speicherplatz von O(n × L²); die Suche kostet genauso viel: Jedes Wort, das die Warteschlange verlässt, erstellt seine L Muster erneut. Bei 5.000 Wörtern mit 10 Buchstaben sind das etwa 500.000 Buchstabenoperationen, gegenüber bis zu 250 Millionen beim paarweisen Vergleich.

Algorithmus

Wenn endWord nicht in wordList enthalten ist, gib 0 zurück.
Füge für jedes Wort in der Liste und für beginWord das Wort dem Bucket jedes seiner L-Muster hinzu.
Beginne die Warteschlange mit beginWord, markiere es als besucht und setze die Länge auf 1.
Verarbeite die Warteschlange Ebene für Ebene. Wenn ein Wort endWord ist, gib die Länge zurück. Füge andernfalls für jedes seiner Muster jedes unbesuchte Wort in diesem Bucket zur nächsten Ebene hinzu, markiere es als besucht und leere den Bucket.
Erhöhe nach jeder Ebene die Länge um 1. Wenn die Warteschlange leer ist, gib 0 zurück.

from collections import defaultdict, deque


def ladderLength(beginWord, endWord, wordList):
    if endWord not in wordList:
        return 0
    size = len(beginWord)
    # "h*t" -> every word that matches it: hot, hat, hit... are one letter apart.
    buckets = defaultdict(list)
    for word in set(wordList) | {beginWord}:
        for i in range(size):
            buckets[word[:i] + "*" + word[i + 1:]].append(word)
    visited = {beginWord}
    queue = deque([beginWord])
    length = 1  # words in the sequence up to the current level
    while queue:
        for _ in range(len(queue)):  # one level: every word at this distance
            word = queue.popleft()
            if word == endWord:
                return length
            for i in range(size):
                pattern = word[:i] + "*" + word[i + 1:]
                for neighbour in buckets[pattern]:
                    if neighbour not in visited:
                        visited.add(neighbour)
                        queue.append(neighbour)
                buckets[pattern] = []  # all of them are visited now: never scan it again
        length += 1
    return 0

Stolperfallen und Grenzfälle

Die meisten falschen Antworten entstehen dadurch, dass das Falsche gezählt wird oder die Regel für endWord übersehen wird.

Die Anzahl der Änderungen statt der Anzahl der Wörter zurückgeben. Von lead zu gold sind es 3 Änderungen und 4 Wörter, und die Antwort ist 4.
Nicht überprüfen, ob endWord in wordList enthalten ist. Im zweiten Beispiel erreicht die Suche von dog aus ein Wort, aber die Antwort ist 0.
Tiefensuche verwenden und die erste gefundene Leiter zurückgeben. Die Tiefensuche verfolgt einen Zweig so weit wie möglich, daher ist ihre erste Leiter oft lang.
Ein Wort erst als besucht markieren, wenn es die Warteschlange verlässt, statt wenn es ihr hinzugefügt wird. Ein Wort in einem vollen Bucket mit 26 Wörtern kann dann bis zu 25-mal in die Warteschlange gelangen, die dadurch weit über n hinaus anwächst.
beginWord unmarkiert lassen, wenn es auch in wordList enthalten ist. Die Suche erreicht es dann zwei Ebenen später erneut und wiederholt Arbeit. Markiere es von Anfang an als besucht.
Auf Wörter testen, die sich in höchstens einem Buchstaben unterscheiden. Jedes Wort unterscheidet sich von sich selbst in null Buchstaben, daher muss die Bedingung genau ein Buchstabe sein.
Entlang der Leiter rekursiv vorgehen. Ein versteckter Test enthält eine kürzeste Leiter mit 1.500 Wörtern, die tief genug ist, um in manchen Sprachen den Aufrufstapel zu überlaufen. BFS benötigt nur eine Warteschlange.

Häufige Fragen4

Warum findet die Breitensuche die kürzeste Wortleiter?

BFS erkundet die Wörter in Runden: zuerst das Startwort, dann jedes Wort, das eine Änderung entfernt ist, und anschließend jedes Wort, das zwei Änderungen entfernt ist. Ein Wort wird zum ersten Mal in der frühesten Runde erreicht, in der es erreichbar ist. Daher entspricht seine Entfernung der kleinstmöglichen Anzahl an Änderungen. Das funktioniert nur, weil jede Änderung gleich viel zählt. Bei unterschiedlichen Kosten pro Schritt bräuchtest du stattdessen den Dijkstra-Algorithmus.

Wie hoch ist die Zeitkomplexität von Word Ladder?

Mit Platzhaltermustern benötigen das Erstellen der Muster und die Suche O(n × L²) Zeit für n Wörter der Länge L, da jedes Wort L Muster aus jeweils L Buchstaben hat. Der Vergleich jedes Wortpaars kostet dagegen O(n² × L), und das Ausprobieren jeder Wortleiter mit Tiefensuche ist exponentiell.

Wie findest du die Wörter, die sich um einen Buchstaben unterscheiden?

Eine Möglichkeit sind die oben genannten Platzhalter-Buckets: Wörter, die ein Muster wie h*t gemeinsam haben, sind Nachbarn. Die andere Möglichkeit besteht darin, jede Position des Wortes durch jeden der 26 Buchstaben zu ersetzen und das Ergebnis in einer Hash-Menge der Wörter nachzuschlagen. Das kostet 26 × L Nachschlagevorgänge pro Wort, wobei jedes Mal L Buchstaben gehasht werden, also insgesamt O(n × 26 × L²). Beides ist besser, als die Wörter mit der gesamten Liste zu vergleichen.

Kann bidirektionale BFS Word Ladder schneller machen?

Ja. Suche gleichzeitig von beginWord und endWord aus, erweitere dabei immer die kleinere Seite um eine Ebene und halte an, wenn ein neues Wort bereits von der anderen Seite erreicht wurde. Die Wortleiter hat dann ein Wort mehr als die zusammen auf beiden Seiten vorgenommenen Änderungen. Wenn jedes Wort etwa b Nachbarn hat und die Wortleiter d Änderungen umfasst, kann eine Suche etwa b^d Wörter erreichen, während zwei Suchen, die sich in der Mitte treffen, etwa 2 × b^(d/2) Wörter erreichen.

Python

def ladderLength(beginWord, endWord, wordList):
    # Schreibe hier den Code

Testfälle

Fall 1

Fall 2

Fall 3

Eingabe

beginWord = "lead"
endWord = "gold"
wordList = ["load", "goad", "gold", "lend", "lewd", "bold"]

Erwartet

Word Ladder

Funktion

Einschränkungen

Beispiele

Tipps

Lösung

Probiere jede Leiter mit Tiefensuche aus

Breitensuche, jeden Paarvergleich

Breitensuche mit Platzhalter-Buckets

Stolperfallen und Grenzfälle

Häufige Fragen4

Ähnliche Aufgaben