Word Ladder
Ti vengono date due parole, beginWord e endWord, e un elenco di parole wordList. Una scala inizia con beginWord, termina con endWord e cambia esattamente una lettera da una parola alla successiva. Ogni parola dopo beginWord deve provenire da wordList, quindi endWord deve esservi presente; beginWord non è necessario che vi sia.
Restituisci il numero di parole nella scala più breve, contando entrambi gli estremi, oppure 0 se non ne esiste nessuna.
Funzione
- beginWordstring
- la prima parola della scala
- endWordstring
- la parola che la scala deve raggiungere
- wordListstring-array
- le parole da cui deve provenire ogni passaggio successivo
- Restituisceinteger
- il numero di parole nella scala più breve, oppure 0 se non ce n’è nessuna
Vincoli
1 ≤ beginWord.length ≤ 10endWorde ogni parola inwordListha la stessa lunghezza dibeginWord.1 ≤ wordList.length ≤ 5000- Tutte le parole contengono solo lettere minuscole dell'alfabeto inglese.
beginWord != endWord- Le parole in
wordListsono tutte diverse.beginWordpotrebbe essere una di esse oppure no.
Esempi
- Input
- beginWord = "lead"endWord = "gold"wordList = ["load", "goad", "gold", "lend", "lewd", "bold"]
- Output
- 4
- Spiegazione
leadegolddifferiscono per tre lettere, quindi una scala richiede almeno 4 parole, elead,load,goad,goldne contiene 4.lendelewdsono vicoli ciechi.
- Input
- beginWord = "cat"endWord = "dog"wordList = ["cot", "cog", "dot", "dig"]
- Output
- 0
- Spiegazione
cat,cot,cogarrivano a una lettera di distanza dadog, madognon è nell’elenco, quindi nessuna scala può terminare lì.
- Input
- beginWord = "ab"endWord = "cd"wordList = ["ab", "cb", "cd", "ad"]
- Output
- 3
- Spiegazione
ab,ad,cdeab,cb,cdcontengono entrambi 3 parole.abè anche nell'elenco, ma l'inizio viene conteggiato una sola volta.
Per approfondire
Puoi restituire una delle sequenze più brevi, con le parole nell'ordine, invece della sua lunghezza?
Suggerimenti
Aprili uno alla volta. Ognuno rivela un po’ di più.
Immagina ogni parola come un punto e traccia una linea tra due parole che differiscono per esattamente una lettera. Che cos’è una scala in questa rappresentazione e qual è la più corta?
La scala più breve è il percorso con il minor numero di righe e tutte le righe contano allo stesso modo. La ricerca in ampiezza raggiunge tutte le parole a un passo di distanza prima di qualsiasi parola a due passi di distanza, quindi la prima volta che raggiunge
endWordha compiuto il minor numero di passi. Contrassegna una parola come visitata nel momento in cui la raggiungi per la prima volta.Confrontare una parola con l’intero elenco per trovare le sue vicine è lento. Invece, nascondi una lettera alla volta:
hot,hatehitdiventano tuttih*t. Inserisci ogni parola nel gruppo corrispondente a ciascuno dei suoi schemi. Le vicine di una parola sono le altre parole nei suoi gruppi. Esegui la ricerca livello per livello a partire dabeginWorde conta i livelli.
Soluzione
Considera le parole come nodi di un grafo, con un arco tra parole che differiscono di una lettera. Ogni arco ha lo stesso costo, quindi la ricerca in ampiezza trova la sequenza più breve. La parte difficile è trovare rapidamente gli archi. Qui sotto, n è il numero di parole e L la loro lunghezza.
Prova ogni scala con la ricerca in profondità
Corretto, ma non termina sui test più grandi
Intuizione
Dalla parola corrente, prova ogni parola non ancora usata che differisce di una lettera e approfondisci la ricerca, mantenendo la lunghezza quando raggiungi endWord. Contrassegna come usate le parole sul percorso e liberale mentre torni indietro. Una volta che esiste una catena di best parole, smetti di estendere i percorsi di best-1 parole.
Questo prova ogni catena senza parole ripetute, e una catena più breve non ripete mai una parola: eliminare la parte tra due copie la accorcerebbe.
Le 26 parole aaa, baa fino a zaa differiscono tutte di una lettera e possono essere ordinate in circa 4 × 10^26 modi. Se endWord non è raggiungibile, il taglio non si attiva mai e la ricerca le prova tutte.
Algoritmo
- Contrassegna
beginWordcome utilizzata se è nell’elenco e impostabesta 0. search(word, length): in corrispondenza diendWord, conservalengthse è inferiore abeste restituisci il controllo. Sebestè impostato elength + 1 ≥ best, restituisci il controllo.- Altrimenti, per ogni parola inutilizzata distante una lettera, contrassegnala, chiama
search(next, length + 1)e rimuovi il contrassegno. - Restituisci
bestdoposearch(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 bestRicerca in ampiezza, confrontando ogni coppia
Corretto, ma non termina sui test più grandi
Intuizione
Una coda esplora le parole in ordine di distanza: tutte le parole a distanza d la lasciano prima che qualsiasi parola a distanza d + 1 lo faccia. Quindi, quando una parola viene raggiunta per la prima volta alla distanza d, tutte le parole più vicine sono già state esplorate, e una scala più corta per raggiungerla l'avrebbe raggiunta prima. La sua distanza è definitiva nel momento in cui entra nella coda, quindi contrassegnala come visitata allora, e la prima volta che compare endWord, la sua distanza è la risposta.
Questa versione trova i vicini di una parola confrontandola con ogni parola dell'elenco, fermandosi alla seconda differenza: O(n² × L), fino a 25 milioni di confronti tra parole per 5.000 parole.
Algoritmo
- Se
endWordnon è inwordList, restituisci 0. - Inserisci
beginWordnella coda con lunghezza 1, contrassegnandolo come visitato se è nell’elenco. - Prendi la parola successiva e confrontala con ogni parola non visitata. Per ciascuna parola distante una lettera: se è
endWord, restituisci lunghezza + 1; altrimenti contrassegnala e inseriscila nella coda con lunghezza + 1. - Se la coda si svuota, restituisci 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 0Ricerca in ampiezza con bucket con caratteri jolly
Intuizione
Due parole differiscono esattamente di una lettera quando, nascondendo la stessa posizione, diventano uguali: hot e hit diventano entrambi h*t. Assegna a ogni parola L schemi, uno per ogni posizione nascosta, e aggiungila a un bucket per ciascuno. I vicini di una parola sono le altre parole nei suoi bucket L, individuate con L ricerche hash invece di scorrere l'elenco.
Nel primo esempio, l*ad contiene load e le*d contiene lend e lewd, quindi il livello 2 è composto da queste tre parole; *oad dà poi goad e go*d dà gold al livello 4.
Una volta esaminato un bucket, tutte le parole al suo interno sono state raggiunte, quindi svuotalo: il bucket di 26 parole *aa viene esaminato una volta, non 26. Il costo è di O(n × L²) in termini di tempo e spazio, circa 500.000 passaggi di lettera per 5.000 parole di 10 lettere.
Algoritmo
- Se
endWordnon è inwordList, restituisci 0. - Raggruppa ogni parola, inclusa
beginWord, in base a ciascuno dei suoi modelliL. - Inserisci
beginWordnella coda, contrassegnata come visitata, con lunghezza 1. - Per ogni parola di un livello: se è
endWord, restituisci la lunghezza. Altrimenti sposta ogni parola non visitata in ciascuno dei suoi gruppi di modelli al livello successivo, contrassegnala come visitata e svuota il gruppo. - Aggiungi 1 alla lunghezza per ogni livello. Se la coda si svuota, restituisci 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
Trappole e casi limite
- Contare i cambiamenti invece delle parole.
lead→goldsono 3 cambiamenti e 4 parole; la risposta è 4. - Saltare il controllo che
endWordsia inwordList. Il secondo esempio arriva acog, a una lettera dadog, ma la risposta è 0. - Contrassegnare una parola come visitata quando esce dalla coda. Una parola nel bucket
*aapuò quindi essere aggiunta fino a 25 volte e la coda cresce ben oltren. - Ricorrere lungo la scala. Una scala minima può contenere migliaia di parole, abbastanza da causare l'overflow dello stack delle chiamate.
Domande frequenti3
Qual è la complessità temporale di Word Ladder?
Con i bucket jolly è O(n × L²) per n parole di lunghezza L: ogni parola ha L schemi di L lettere. Confrontare ogni coppia di parole costa O(n² × L), mentre provare ogni scala con una ricerca in profondità è esponenziale.
Come trovi le parole che differiscono di una sola lettera?
I gruppi di caratteri jolly sono un metodo. L'altro consiste nel sostituire ogni posizione con ciascuna delle 26 lettere e cercare il risultato in un insieme hash delle parole: 26 × L ricerche di L lettere per parola, O(n × 26 × L²) in totale. Entrambi sono più efficienti di una scansione dell'elenco.
La ricerca BFS bidirezionale può rendere Word Ladder più veloce?
Sì. Cerca da entrambe le estremità contemporaneamente, espandendo sempre di un livello il lato più piccolo, e fermati quando i due lati si incontrano. Con circa b vicini per parola e d cambiamenti, una ricerca può raggiungere circa b^d parole; due ricerche che si incontrano a metà raggiungono circa 2 × b^(d/2).
Problemi simili
Problemi che usano le stesse idee. Risolverne due o tre è ciò che fissa uno schema.
def ladderLength(beginWord, endWord, wordList):
# Scrivi il codice quiTest #1
Test #2
Test #3
Argomenti
beginWord = "lead" endWord = "gold" wordList = ["load", "goad", "gold", "lend", "lewd", "bold"]
Output atteso
4