Word Ladder

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

Mit Platzhaltereimern beträgt der Aufwand O(n × L²) für n Wörter der Länge L : Jedes Wort hat L Muster mit jeweils L Buchstaben. Der Vergleich jedes Wortpaars kostet O(n² × L) , und das Ausprobieren jeder Leiter mit Tiefensuche ist exponentiell.

SchwerGraphen Warteschlange

+10

Du erhältst zwei Wörter, beginWord und endWord, sowie eine Wortliste wordList. Eine Wortleiter beginnt mit beginWord, endet mit endWord und ändert von einem Wort zum nächsten genau einen Buchstaben. Jedes Wort nach beginWord muss aus wordList stammen, also muss endWord darin enthalten sein; beginWord muss es nicht sein.

Gib die Anzahl der Wörter in der kürzesten Wortleiter zurück, wobei beide Enden mitgezählt werden, oder 0, falls es keine gibt.

Funktion

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

beginWordstring: das erste Wort der Leiter
endWordstring: das Wort, das die Wortleiter 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 hat 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 benötigt eine Wortleiter mindestens 4 Wörter, und lead, load, goad, gold sind 4. lend und lewd sind Sackgassen.

Eingabe: beginWord = "cat"endWord = "dog"wordList = ["cot", "cog", "dot", "dig"]
Ausgabe: 0
Erklärung: cat, cot, cog kommen dog bis auf einen Buchstaben nahe, aber dog steht nicht in der Liste, daher kann dort keine Wortleiter 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 nur einmal gezählt.

Weiterführende Frage

Kannst du eine kürzeste Leiter selbst zurückgeben, also die Wörter in der richtigen Reihenfolge, statt ihrer 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, wobei zwischen Wörtern, die sich um einen Buchstaben unterscheiden, eine Kante besteht. Jede Kante kostet gleich viel, daher findet die Breitensuche die kürzeste Leiter. Die Schwierigkeit besteht darin, die Kanten schnell zu finden. Im Folgenden 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

Probiere vom aktuellen Wort aus jedes unbenutzte Wort aus, das sich in einem Buchstaben unterscheidet, und gehe tiefer, wobei du die Länge beibehältst, wenn du endWord erreichst. Markiere Wörter auf dem Pfad als verwendet und gib sie wieder frei, wenn du zurückgehst. Sobald eine Leiter aus best Wörtern existiert, erweitere keine Pfade aus best-1 Wörtern mehr.

Damit werden alle Leitern ohne wiederholte Wörter ausprobiert, und eine kürzeste Leiter wiederholt niemals ein Wort: Entfernt man den Abschnitt zwischen zwei Vorkommen desselben Wortes, wird sie kürzer.

Die 26 Wörter aaa, baa bis zaa unterscheiden sich jeweils in genau einem Buchstaben und lassen sich in etwa 4 × 10^26 Reihenfolgen anordnen. Ist endWord nicht erreichbar, wird der Abbruch nie ausgelöst und die Suche probiert sie alle aus.

Algorithmus

Markiere beginWord als verwendet, wenn es in der Liste steht, und setze best auf 0.
search(word, length): Bei endWord behalte length, wenn es besser als best ist, und kehre zurück. Wenn best gesetzt ist und length + 1 ≥ best gilt, kehre zurück.
Andernfalls markiere für jedes unbenutzte Wort, das sich um einen Buchstaben unterscheidet, dieses Wort, rufe search(next, length + 1) auf und markiere es wieder als unbenutzt.
Gib best nach search(beginWord, 1) zurück.

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, Vergleich jedes Paars

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

Idee

Eine Warteschlange erkundet die Wörter nach ihrer Entfernung: Alle Wörter mit der Entfernung d verlassen sie, bevor ein Wort mit der Entfernung d + 1 an der Reihe ist. Wenn ein Wort also zum ersten Mal in der Entfernung d erreicht wird, wurden bereits alle näheren Wörter erkundet, und eine kürzere Wortleiter hätte es früher erreicht. Seine Entfernung steht endgültig fest, sobald es in die Warteschlange kommt. Markiere es also dann als besucht, und wenn endWord zum ersten Mal auftaucht, ist seine Entfernung die Antwort.

Diese Version findet die Nachbarn eines Wortes, indem sie es mit jedem Wort in der Liste vergleicht und beim zweiten Unterschied abbricht: O(n² × L), also bis zu 25 Millionen Wortvergleiche bei 5.000 Wörtern.

Algorithmus

Wenn endWord nicht in wordList enthalten ist, gib 0 zurück.
Füge beginWord mit der Länge 1 zur Warteschlange hinzu und markiere es als besucht, wenn es in der Liste enthalten ist.
Nimm das nächste Wort und vergleiche es mit jedem unbesuchten Wort. Für jedes Wort, das sich in einem Buchstaben unterscheidet: Gib length + 1 zurück, wenn es endWord ist; andernfalls markiere es als besucht und füge es mit der Länge length + 1 zur Warteschlange hinzu.
Wenn die Warteschlange leer ist, 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

Zwei Wörter unterscheiden sich genau dann um einen Buchstaben, wenn sie gleich werden, sobald man dieselbe Position ausblendet: hot und hit werden beide zu h*t. Erzeuge für jedes Wort L Muster, eines pro ausgeblendeter Position, und füge es jeweils einem Bucket hinzu. Die Nachbarn eines Wortes sind die anderen Wörter in seinen L-Buckets, die durch L Hash-Lookups statt durch einen Durchlauf über die Liste gefunden werden.

Im ersten Beispiel enthält l*ad load und le*d enthält lend und lewd, also besteht Ebene 2 aus diesen drei Wörtern; *oad liefert dann goad, und go*d liefert gold auf Ebene 4.

Sobald ein Bucket durchlaufen wurde, ist jedes Wort darin erreicht, also leere ihn: Der Bucket *aa mit 26 Wörtern wird einmal durchlaufen, nicht 26-mal. Der Aufwand beträgt O(n × L²) Zeit und Speicherplatz, etwa 500.000 Buchstabenschritte für 5.000 Wörter mit 10 Buchstaben.

Algorithmus

Wenn endWord nicht in wordList enthalten ist, gib 0 zurück.
Ordne jedes Wort, einschließlich beginWord, jedem seiner L-Muster zu.
Füge beginWord als besucht markiert mit der Länge 1 zur Warteschlange hinzu.
Für jedes Wort einer Ebene: Gib bei endWord die Länge zurück. Andernfalls verschiebe jedes unbesuchte Wort aus jedem seiner Muster-Buckets auf die nächste Ebene, markiere es als besucht und leere den Bucket.
Addiere pro Ebene 1 zur Länge. 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

Änderungen statt Wörter zählen. Von lead zu gold sind es 3 Änderungen und 4 Wörter; die Antwort ist 4.
Nicht prüfen, ob endWord in wordList enthalten ist. Das zweite Beispiel erreicht cog, das sich um einen Buchstaben von dog unterscheidet, aber die Antwort ist 0.
Ein Wort erst als besucht markieren, wenn es die Warteschlange verlässt. Ein Wort im Bucket *aa kann dann bis zu 25-mal hinzugefügt werden, und die Warteschlange wächst weit über n hinaus.
Entlang der Wortleiter rekursiv vorgehen. Eine kürzeste Wortleiter kann Tausende Wörter lang sein – genug, um den Aufrufstapel zu überlaufen.

Häufige Fragen3

Wie hoch ist die Zeitkomplexität von Word Ladder?

Mit Platzhaltereimern beträgt der Aufwand O(n × L²) für n Wörter der Länge L: Jedes Wort hat L Muster mit jeweils L Buchstaben. Der Vergleich jedes Wortpaars kostet O(n² × L), und das Ausprobieren jeder Leiter mit Tiefensuche ist exponentiell.

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

Wildcard-Buckets sind eine Möglichkeit. Die andere besteht darin, jede Position durch jeden der 26 Buchstaben zu ersetzen und das Ergebnis in einer Hashtabelle der Wörter nachzuschlagen: 26 × L Nachschlagevorgänge mit L Buchstaben pro Wort, insgesamt O(n × 26 × L²). Beides ist schneller als ein Durchlauf durch die Liste.

Kann bidirektionale Breitensuche Word Ladder beschleunigen?

Ja. Suche gleichzeitig von beiden Enden aus, erweitere dabei immer die kleinere Seite um eine Ebene und höre auf, wenn sich die beiden Seiten treffen. Bei etwa b Nachbarn pro Wort und d Änderungen kann eine Suche etwa b^d Wörter berühren; zwei Suchen, die sich in der Mitte treffen, berühren etwa 2 × b^(d/2).

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

Test #1

Test #2

Test #3

Argumente

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

Erwartete Ausgabe

Word Ladder

Funktion

Einschränkungen

Beispiele

Tipps

Lösung

Probiere jede Leiter mit Tiefensuche aus

Breitensuche, Vergleich jedes Paars

Breitensuche mit Platzhalter-Buckets

Stolperfallen und Grenzfälle

Häufige Fragen3

Ähnliche Aufgaben