Word Ladder

+10

Otrzymujesz dwa słowa: beginWord i endWord, oraz listę słów wordList. Ścieżka zaczyna się od beginWord, kończy na endWord i każdorazowo zmienia dokładnie jedną literę z jednego słowa na następne. Każde słowo po beginWord musi pochodzić z wordList, więc endWord musi się na niej znajdować; beginWord nie musi.

Zwróć liczbę słów w najkrótszej ścieżce, licząc oba końce, lub 0, jeśli taka ścieżka nie istnieje.

Funkcja

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

beginWordstring: pierwsze słowo drabiny
endWordstring: słowo „drabina” musi sięgać
wordListstring-array: słowa, z których musi pochodzić każdy kolejny krok
Zwracainteger: liczba słów w najkrótszej drabince albo 0, jeśli jej nie ma

Ograniczenia

1 ≤ beginWord.length ≤ 10
endWord i każde słowo w wordList ma taką samą długość jak beginWord.
1 ≤ wordList.length ≤ 5000
Wszystkie słowa zawierają wyłącznie małe litery alfabetu angielskiego.
beginWord != endWord
Słowa w wordList są różne. beginWord może być jednym z nich, ale nie musi.

Przykłady

Wejście: beginWord = "lead"endWord = "gold"wordList = ["load", "goad", "gold", "lend", "lewd", "bold"]
Wyjście: 4
Wyjaśnienie: lead i gold różnią się trzema literami, więc drabinka wymaga co najmniej 4 słów, a lead, load, goad, gold to 4 słowa. lend i lewd prowadzą donikąd.

Wejście: beginWord = "cat"endWord = "dog"wordList = ["cot", "cog", "dot", "dig"]
Wyjście: 0
Wyjaśnienie: cat, cot, cog różnią się od dog tylko jedną literą, ale dog nie ma na liście, więc żadna drabinka nie może się tam kończyć.

Wejście: beginWord = "ab"endWord = "cd"wordList = ["ab", "cb", "cd", "ad"]
Wyjście: 3
Wyjaśnienie: ab, ad, cd oraz ab, cb, cd zawierają po 3 słowa. ab również znajduje się na liście, ale słowo początkowe jest liczone tylko raz.

Pytanie dodatkowe

Czy możesz zwrócić jedną najkrótszą drabinkę w postaci kolejnych słów, zamiast jej długości?

Podpowiedzi

Otwieraj je po kolei. Każda zdradza trochę więcej.

Otwarte: 0 z 3

Rozwiązanie

Potraktuj słowa jako wierzchołki grafu, a między słowami różniącymi się jedną literą umieść krawędź. Każda krawędź ma taki sam koszt, więc wyszukiwanie wszerz znajduje najkrótszą drabinkę. Trudność polega na szybkim znajdowaniu krawędzi. Poniżej n oznacza liczbę słów, a L ich długość.

Wypróbuj każdą ścieżkę za pomocą przeszukiwania w głąb

Poprawne, ale nie kończy się na największych testach

Intuicja

Z bieżącego słowa spróbuj każdego nieużytego słowa różniącego się jedną literą i przejdź głębiej, zachowując długość po dotarciu do endWord. Oznaczaj słowa na ścieżce jako użyte, a podczas cofania się zwalniaj je. Gdy istnieje już drabina złożona z best słów, przestań rozwijać ścieżki złożone z best-1 słów.

Ta metoda sprawdza każdą drabinę bez powtórzonych słów, a najkrótsza drabina nigdy nie zawiera powtórzeń: usunięcie fragmentu między dwoma wystąpieniami tego samego słowa skróciłoby ją.

Wszystkie 26 słów od aaa do zaa, włącznie z baa, różnią się od siebie jedną literą i można je uporządkować na około 4 × 10^26 sposobów. Jeśli nie da się dotrzeć do endWord, warunek odcięcia nigdy nie zadziała i wyszukiwanie sprawdzi je wszystkie.

Algorytm

Oznacz beginWord jako użyte, jeśli znajduje się na liście, i ustaw best na 0.
search(word, length): przy endWord zachowaj length, jeśli jest mniejsze od best, i zwróć wynik. Jeśli ustawiono best i length + 1 ≥ best, zwróć wynik.
W przeciwnym razie dla każdego nieużytego słowa różniącego się jedną literą oznacz je jako użyte, wywołaj search(next, length + 1) i oznacz je jako nieużyte.
Zwróć best po wywołaniu search(beginWord, 1).

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

Przeszukiwanie wszerz, porównywanie każdej pary

Poprawne, ale nie kończy się na największych testach

Intuicja

Kolejka przetwarza słowa w kolejności odległości: wszystkie słowa w odległości d opuszczają ją, zanim pojawi się w niej jakiekolwiek słowo w odległości d + 1. Gdy więc słowo zostaje osiągnięte po raz pierwszy w odległości d, wszystkie bliższe słowa zostały już przetworzone, a krótsza drabinka do niego dotarłaby wcześniej. Jego odległość jest ostateczna w chwili, gdy trafia do kolejki, więc oznacz je wtedy jako odwiedzone, a odległość przy pierwszym pojawieniu się endWord jest odpowiedzią.

Ta wersja znajduje sąsiadów słowa, porównując je z każdym słowem z listy i kończąc po drugiej różnicy: O(n² × L), czyli do 25 milionów porównań słów dla 5,000 słów.

Algorytm

Jeśli endWord nie ma w wordList, zwróć 0.
Umieść beginWord w kolejce z długością 1; oznacz go jako odwiedzony, jeśli znajduje się na liście.
Weź następne słowo i porównaj je z każdym nieodwiedzonym słowem. Dla każdego słowa różniącego się jedną literą: jeśli jest to endWord, zwróć długość + 1; w przeciwnym razie oznacz je i umieść w kolejce z długością + 1.
Jeśli kolejka się opróżni, zwróć 0.

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

Przeszukiwanie wszerz z kubełkami symboli wieloznacznych

Intuicja

Dwa słowa różnią się dokładnie jedną literą wtedy, gdy ukrycie tej samej pozycji sprawia, że stają się równe: hot i hit dają h*t. Utwórz dla każdego słowa L wzorców, po jednym dla każdej ukrytej pozycji, i dodaj je do odpowiednich kubełków. Sąsiedzi słowa to pozostałe słowa w jego L kubełkach, znajdowane za pomocą L wyszukiwań w tablicy mieszającej zamiast przechodzenia przez całą listę.

W pierwszym przykładzie l*ad zawiera load, a le*d zawiera lend i lewd, więc na poziomie 2 są te trzy słowa; *oad daje następnie goad, a go*d daje gold na poziomie 4.

Po przeskanowaniu kubełka docierasz do każdego słowa w nim, więc opróżnij go: kubełek *aa zawierający 26 słów jest skanowany raz, a nie 26 razy. Złożoność czasowa i pamięciowa wynosi O(n × L²), czyli około 500 000 kroków po literach dla 5 000 słów o długości 10 liter.

Algorytm

Jeśli endWord nie ma w wordList, zwróć 0.
Umieść każde słowo, w tym beginWord, w grupie odpowiadającej każdemu z jego wzorców L.
Dodaj beginWord do kolejki, oznacz jako odwiedzone i ustaw długość na 1.
Dla każdego słowa na danym poziomie: jeśli jest to endWord, zwróć długość. W przeciwnym razie przenieś każde nieodwiedzone słowo z każdego z jego kubełków wzorców na następny poziom, oznacz je jako odwiedzone i opróżnij kubełek.
Zwiększ długość o 1 na każdym poziomie. Jeśli kolejka się opróżni, zwróć 0.

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

Pułapki i przypadki brzegowe

Liczenie zmian zamiast słów. Od lead do gold są 3 zmiany i 4 słowa; odpowiedź to 4.
Pominięcie sprawdzenia, czy endWord znajduje się w wordList. W drugim przykładzie można dotrzeć do cog, który różni się jedną literą od dog, ale odpowiedź wynosi 0.
Oznaczanie słowa jako odwiedzonego dopiero po usunięciu go z kolejki. Słowo w kubełku *aa może wtedy dołączyć nawet 25 razy, a kolejka rośnie znacznie powyżej n.
Rekurencyjne przechodzenie po drabinie. Najkrótsza drabina może mieć tysiące słów, co wystarczy, by przepełnić stos wywołań.

Najczęstsze pytania3

Jaka jest złożoność czasowa Word Ladder?

Przy użyciu kubełków z symbolami wieloznacznymi złożoność wynosi O(n × L²) dla n słów o długości L: każde słowo ma L wzorców składających się z L liter. Porównanie każdej pary słów kosztuje O(n² × L), a próbowanie każdej drabinki za pomocą przeszukiwania w głąb ma złożoność wykładniczą.

Jak znaleźć słowa różniące się o jedną literę?

Kubełki z symbolami wieloznacznymi to jeden ze sposobów. Drugim jest zastąpienie każdej pozycji każdą z 26 liter i wyszukanie wyniku w zbiorze haszującym słów: 26 × L wyszukiwań słów o długości L, łącznie O(n × 26 × L²). Oba sposoby są lepsze niż przejście przez całą listę.

Czy dwukierunkowe BFS może przyspieszyć Word Ladder?

Tak. Przeszukuj jednocześnie od obu końców, za każdym razem rozszerzając mniejszą stronę o jeden poziom, i zakończ, gdy obie strony się spotkają. Przy około b sąsiadach na słowo i d zmianach jedno wyszukiwanie może dotknąć około b^d słów; dwa wyszukiwania, które spotkają się w połowie, dotykają około 2 × b^(d/2).

def ladderLength(beginWord, endWord, wordList):
    # Wpisz kod tutaj

Test #1

Test #2

Test #3

Argumenty

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

Oczekiwany wynik

Word Ladder

Funkcja

Ograniczenia

Przykłady

Podpowiedzi

Rozwiązanie

Wypróbuj każdą ścieżkę za pomocą przeszukiwania w głąb

Przeszukiwanie wszerz, porównywanie każdej pary

Przeszukiwanie wszerz z kubełkami symboli wieloznacznych

Pułapki i przypadki brzegowe

Najczęstsze pytania3

Podobne zadania