Word Ladder
Otrzymujesz dwa słowa: beginWord i endWord, oraz listę słów wordList. Drabinka to sekwencja słów, która zaczyna się od beginWord, kończy na endWord i zmienia dokładnie jedną literę z każdego słowa na następne. Każde słowo po beginWord musi pochodzić z wordList.
Zwróć liczbę słów w najkrótszej drabince, licząc oba końce, lub 0, jeśli taka drabinka nie istnieje. Na przykład cold, cord, card to drabinka składająca się z 3 słów. beginWord nie musi znajdować się w wordList, ale endWord musi.
Funkcja
- beginWordstring
- pierwsze słowo drabinki
- endWordstring
- słowo the ladder musi dosięgnąć
- wordListstring-array
- słowa, spośród których trzeba wybierać na każdym kolejnym kroku
- Zwracainteger
- liczba słów w najkrótszym łańcuchu lub 0, jeśli taki nie istnieje
Ograniczenia
1 ≤ beginWord.length ≤ 10endWordoraz każde słowo zwordListmają taką samą długość jakbeginWord.1 ≤ wordList.length ≤ 5000- Wszystkie słowa zawierają wyłącznie małe litery alfabetu angielskiego.
beginWord != endWord- Słowa w
wordListsą różne.beginWordmoże, ale nie musi być jednym z nich.
Przykłady
- Wejście
- beginWord = "lead"endWord = "gold"wordList = ["load", "goad", "gold", "lend", "lewd", "bold"]
- Wyjście
- 4
- Wyjaśnienie
leadigoldróżnią się trzema literami, więc żadna drabinka nie ma mniej niż 4 słowa, alead,load,goad,goldmają dokładnie 4.lendilewdrównież różnią się odleadjedną literą, ale żadne z nich nie prowadzi do niczego nowego, a doboldmożna dotrzeć tylko z samegogold.
- Wejście
- beginWord = "cat"endWord = "dog"wordList = ["cot", "cog", "dot", "dig"]
- Wyjście
- 0
- Wyjaśnienie
cat,cot,cogróżnią się oddogjedną literą, aledognie 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,cdorazab,cb,cdobejmują po 3 słowa.abrównież znajduje się na liście, ale początek jest liczony tylko raz w obu przypadkach.
+14 ukrytych testów przy wysłaniu
Pytanie dodatkowe
Czy możesz zwrócić jedną z najkrótszych ścieżek, czyli słowa w kolejności, a nie tylko jej długość?
Podpowiedzi
Otwieraj je po kolei. Każda zdradza trochę więcej.
Wyobraź sobie każde słowo jako punkt i narysuj linię między dwoma słowami, które różnią się dokładnie jedną literą. Czym jest drabina na tym rysunku i jaka jest najkrótsza?
Najkrótsza drabina to ścieżka z najmniejszą liczbą wierszy, a każdy wiersz liczy się tak samo. Wyszukiwanie wszerz dociera do wszystkich słów oddalonych o jeden krok, zanim dotrze do jakiegokolwiek słowa oddalonego o dwa kroki, więc gdy po raz pierwszy dociera do
endWord, ma za sobą najmniej kroków. Oznacz słowo jako odwiedzone w chwili, gdy po raz pierwszy do niego dotrzesz.Porównywanie słowa z całą listą, aby znaleźć jego sąsiadów, jest powolne. Zamiast tego ukrywaj po jednej literze:
hot,hatihitwszystkie stają sięh*t. Umieść każde słowo w kubełku odpowiadającym każdemu z jego wzorców. Sąsiadami słowa są pozostałe słowa w jego kubełkach. Przeprowadzaj wyszukiwanie poziom po poziomie, zaczynając odbeginWord, i licz poziomy.
Rozwiązanie
Potraktuj słowa jako wierzchołki grafu, a krawędź umieść między dwoma słowami różniącymi się jedną literą. Drabina jest więc ścieżką od beginWord do endWord, a każda krawędź ma ten sam koszt, dlatego najkrótsza drabina to ścieżka z najmniejszą liczbą krawędzi. Przeszukiwanie wszerz znajduje właśnie taką ścieżkę. Trudność polega na szybkim znajdowaniu krawędzi: porównanie każdej pary spośród 5,000 słów oznacza 25 milionów porównań, więc najlepsze rozwiązanie znajduje sąsiadów za pomocą wzorców z symbolami wieloznacznymi. Poniżej n oznacza liczbę słów, a L ich długość.
Wypróbuj każdą drabinkę, używając przeszukiwania w głąb
Poprawne, ale nie kończy się na największych testach
Intuicja
Zacznij od beginWord. Dla bieżącego słowa wypróbuj każde niewykorzystane słowo różniące się od niego jedną literą i przejdź dalej. Gdy dotrzesz do endWord, zapisz długość łańcucha, jeśli jest najkrótszy z dotychczas znalezionych. Oznacz słowa na bieżącej ścieżce jako użyte, aby łańcuch nie zapętlił się, a gdy się z niego wycofasz, zwolnij każde słowo, by mogły z niego korzystać inne łańcuchy. Gdy znajdziesz łańcuch składający się z best słów, przestań przedłużać każdą ścieżkę, która ma już best-1 słów: nie może ona zakończyć się krócej.
To rozwiązanie jest poprawne, ponieważ sprawdza każdy łańcuch, w którym żadne słowo się nie powtarza, a najkrótszy łańcuch nigdy nie zawiera powtórzeń: jeśli jakieś słowo pojawiłoby się dwa razy, usunięcie fragmentu między tymi wystąpieniami dałoby krótszy łańcuch.
To rozwiązanie działa wolno, ponieważ liczba łańcuchów rośnie lawinowo. Weźmy 26 słów różniących się tylko pierwszą literą: aaa, baa aż do zaa: każda para różni się jedną literą, więc wyszukiwanie może przechodzić przez nie w dowolnej kolejności, zanim pójdzie dalej, a 26 słów można uporządkować na około 4 × 10^26 sposobów. Ograniczenie pomaga dopiero po znalezieniu jakiegoś łańcucha. Jeśli w ogóle nie da się dotrzeć do endWord, nic nie zostanie odcięte, a lista składająca się z 34 słów już przekracza możliwości wyszukiwania. Rekurencja może też sięgać tak głęboko, jak długi jest łańcuch, a ten może mieć tysiące słów.
Algorytm
- Oznacz
beginWordjako użyte, jeśli znajduje się na liście, i ustawbestna 0. - Napisz
search(word, length). Jeśliwordjest równeendWord, zachowajlength, jeśli jest mniejsze odbest, i zakończ działanie. - Jeśli
bestnie jest równe 0 ilength + 1 ≥ best, zakończ działanie: ta ścieżka nie może wygrać. - Dla każdego nieużytego słowa różniącego się od
wordjedną literą oznacz je jako użyte, wywołajsearch(next, length + 1), a następnie oznacz je jako nieużyte. - Wywołaj
search(beginWord, 1)i zwróćbest, które pozostaje równe 0, jeśli nie istnieje żadna drabinka.
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 bestWyszukiwanie wszerz — porównywanie każdej pary
Poprawne, ale nie kończy się na największych testach
Intuicja
Przeszukiwanie wszerz analizuje słowa w kolejności rosnącej odległości. Najpierw beginWord — drabinka z 1 słowem. Następnie każde słowo oddalone od niego o jedną literę — drabinki z 2 słowami. Potem każde nowe słowo oddalone o jedną literę od tych słów — drabinki z 3 słowami i tak dalej. Kolejka zachowuje tę kolejność: słowa opuszczają ją w kolejności, w jakiej do niej trafiły, więc wszystkie słowa w odległości d opuszczają ją przed jakimkolwiek słowem w odległości d + 1.
Właśnie dlatego pierwsza drabinka znaleziona przez BFS jest najkrótsza. Gdy słowo zostaje po raz pierwszy osiągnięte w odległości d, wszystkie słowa bliższe niż d zostały już przeanalizowane, więc gdyby istniała do niego krótsza drabinka, wyszukiwanie dotarłoby do tego słowa wcześniej. To samo rozumowanie sprawia, że bezpiecznie jest oznaczyć słowo jako odwiedzone w chwili, gdy trafia do kolejki: jego odległość jest już ostateczna, a dotarcie do niego później może oznaczać tylko dłuższą drogę. Każde słowo trafia więc do kolejki tylko raz, a gdy tylko endWord pojawi się jako sąsiad, jego odległość jest odpowiedzią.
Ta wersja znajduje sąsiadów danego słowa, porównując je kolejno z każdym słowem z listy, litera po literze, i kończąc przy drugiej różnicy. Każde z maksymalnie n słów opuszczających kolejkę wymaga n porównań obejmujących do L liter, co daje łącznie O(n² × L). Przy 5 000 słów i wyszukiwaniu, które odwiedza większość z nich, oznacza to maksymalnie 25 milionów porównań słów. Język kompilowany radzi sobie z tym szybko, ale Python potrzebuje kilku sekund przy największym teście.
Algorytm
- Jeśli
endWordnie ma wwordList, zwróć 0. - Umieść
beginWordw kolejce z długością 1. Oznacz je jako odwiedzone, jeśli znajduje się na liście. - Pobierz następne słowo i jego długość z kolejki.
- Porównaj je z każdym nieodwiedzonym słowem na liście. Dla każdego, które różni się dokładnie jedną literą: jeśli jest to
endWord, zwróć length + 1; w przeciwnym razie oznacz je jako odwiedzone i dodaj je z długością length + 1. - Jeśli kolejka się opróżni,
endWordjest nieosiągalne: 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 0Przeszukiwanie wszerz z koszykami symboli wieloznacznych
Intuicja
Zachowaj przeszukiwanie wszerz i spraw, by znajdowanie sąsiadów było tanie. Dwa słowa różnią się dokładnie jedną literą wtedy i tylko wtedy, gdy ukrycie tej samej pozycji w obu sprawia, że są równe: hot i hit stają się h*t. Utwórz więc dla każdego słowa L wzorców, po jednym dla każdej ukrytej pozycji, i dodaj słowo do koszyka dla każdego wzorca. Sąsiadami słowa są pozostałe słowa w jego L koszykach, znajdowane przez L wyszukiwań skrótowych zamiast przeglądania całej listy.
Oto wyszukiwanie na pierwszym przykładzie. Słowo lead ma wzorce *ead, l*ad, le*d i lea*. Koszyk l*ad zawiera load, a koszyk le*d zawiera lend i lewd, więc na poziomie 2 są te trzy słowa. Z load koszyk *oad daje goad na poziomie 3, a z goad wzorzec go*d daje gold na poziomie 4.
Jeszcze jedna oszczędność: gdy koszyk danego słowa został przeskanowany, dotarto już do każdego znajdującego się w nim słowa, więc opróżnij go. Późniejsze słowa współdzielące ten wzorzec i tak nie znalazłyby tam niczego nowego. W teście, w którym słowa aaa, baa aż do zaa współdzielą wzorzec *aa, ten 26-elementowy koszyk jest skanowany raz zamiast 26 razy. W rezultacie wyszukiwanie odczytuje każdy wpis koszyka spośród n × L najwyżej raz.
Tworzenie wzorców wymaga n × L ciągów po L liter, czasu i pamięci O(n × L²), a wyszukiwanie kosztuje tyle samo: każde słowo pobierane z kolejki ponownie tworzy swoje L wzorców. Dla 5,000 słów o długości 10 liter to około 500,000 kroków przetwarzania liter, w porównaniu z maksymalnie 250 milionami przy porównywaniu parami.
Algorytm
- Jeśli
endWordnie znajduje się wwordList, zwróć 0. - Dla każdego słowa na liście oraz dla
beginWorddodaj słowo do kubełka odpowiadającego każdemu z jego wzorcówL. - Rozpocznij kolejkę od
beginWord, oznacz je jako odwiedzone i ustaw długość na 1. - Przetwarzaj kolejkę poziom po poziomie. Jeśli słowo to
endWord, zwróć długość. W przeciwnym razie dla każdego z jego wzorców dodaj do następnego poziomu każde nieodwiedzone słowo z odpowiadającego mu kubełka, oznacz je jako odwiedzone i opróżnij kubełek. - Po każdym poziomie zwiększ długość o 1. 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
Większość błędnych odpowiedzi wynika z liczenia niewłaściwych rzeczy lub z niezastosowania się do zasady dotyczącej endWord.
- Zwracanie liczby zmian zamiast liczby słów. Przejście od
leaddogoldwymaga 3 zmian i obejmuje 4 słowa, więc odpowiedź to 4. - Brak sprawdzenia, czy
endWordznajduje się wwordList. W drugim przykładzie wyszukiwanie zmienia jedną literę wdog, ale odpowiedź wynosi 0. - Używanie przeszukiwania w głąb i zwracanie pierwszego znalezionego ciągu. DFS podąża jedną gałęzią tak daleko, jak to możliwe, dlatego znaleziony jako pierwszy ciąg często jest długi.
- Oznaczanie słowa jako odwiedzonego, gdy opuszcza kolejkę, zamiast gdy do niej trafia. Słowo z pełnego kubełka zawierającego 26 słów może wtedy trafić do kolejki nawet 25 razy, a kolejka rozrasta się znacznie bardziej niż
n. - Pozostawienie
beginWordbez oznaczenia, gdy znajduje się również wwordList. Wyszukiwanie dociera wtedy do niego ponownie dwa poziomy później i powtarza pracę. Oznacz je jako odwiedzone od początku. - Sprawdzanie, czy słowa różnią się co najwyżej jedną literą. Każde słowo różni się od samego siebie zerową liczbą liter, więc warunek powinien wymagać dokładnie jednej różnicy.
- Rekurencyjne przechodzenie po ciągu. W jednym z ukrytych testów najkrótszy ciąg ma 1,500 słów, co jest wystarczająco głębokie, by przepełnić stos wywołań w niektórych językach. BFS potrzebuje tylko kolejki.
Najczęstsze pytania4
Dlaczego wyszukiwanie wszerz znajduje najkrótszą drabinkę słów?
BFS eksploruje słowa rundami: najpierw słowo początkowe, potem każde słowo oddalone o jedną zmianę, a następnie każde słowo oddalone o dwie zmiany. Do danego słowa docieramy po raz pierwszy w najwcześniejszej rundzie, w której można do niego dotrzeć, więc jego odległość oznacza najmniejszą możliwą liczbę zmian. Działa to tylko dlatego, że każda zmiana ma taki sam koszt. Przy różnych kosztach poszczególnych kroków potrzebny byłby zamiast tego algorytm Dijkstry.
Jaka jest złożoność czasowa Word Ladder?
W przypadku kubełków z symbolami wieloznacznymi tworzenie wzorców i przeszukiwanie zajmuje O(n × L²) czasu dla n słów o długości L, ponieważ każde słowo ma L wzorców składających się z L liter. Porównywanie każdej pary słów kosztuje natomiast O(n² × L), a próbowanie każdej drabinki za pomocą wyszukiwania w głąb ma złożoność wykładniczą.
Jak znaleźć słowa różniące się o jedną literę?
Jednym ze sposobów są opisane wyżej kubełki z symbolami wieloznacznymi: słowa, które pasują do wzorca takiego jak h*t, są sąsiadami. Drugim sposobem jest zastąpienie każdej pozycji w słowie każdą z 26 liter i wyszukanie wyniku w zbiorze haszującym słów. Kosztuje to 26 × L wyszukiwań na słowo, z których każde haszuje L liter, czyli łącznie O(n × 26 × L²). Oba sposoby są lepsze niż porównywanie ze wszystkimi słowami z listy.
Czy dwukierunkowe BFS może przyspieszyć Word Ladder?
Tak. Wyszukuj jednocześnie od beginWord i endWord, zawsze rozszerzając mniejszą stronę o jeden poziom, i zakończ, gdy nowe słowo zostało już osiągnięte przez drugą stronę. Drabina zawiera wtedy o jedno słowo więcej niż łączna liczba zmian wykonanych po obu stronach. Jeśli każde słowo ma około b sąsiadów, a drabina wymaga d zmian, jedno wyszukiwanie może objąć około b^d słów, podczas gdy dwa wyszukiwania, które spotykają się w połowie, obejmują około 2 × b^(d/2).
Podobne zadania
Zadania oparte na tych samych pomysłach. Rozwiązanie dwóch lub trzech utrwala schemat.
Python
def ladderLength(beginWord, endWord, wordList):
# Wpisz kod tutajPrzypadek 1
Przypadek 2
Przypadek 3
Wejście
beginWord = "lead" endWord = "gold" wordList = ["load", "goad", "gold", "lend", "lewd", "bold"]
Oczekiwane
4