Word Ladder

Q: La BFS bidirezionale può rendere più veloce Word Ladder?

Sì. Cerca contemporaneamente da beginWord e da endWord , ampliando sempre di un livello il lato più piccolo, e fermati quando una nuova parola è già stata raggiunta dall’altro lato. La sequenza ha quindi una parola in più rispetto alle modifiche effettuate complessivamente su entrambi i lati. Se ogni parola ha circa b vicini e la sequenza richiede d modifiche, una ricerca può visitare circa b^d parole, mentre due ricerche che si incontrano a metà ne visitano circa 2 × b^(d/2) .

DifficileGrafi Coda

+10

Ti vengono date due parole, beginWord e endWord, e un elenco di parole wordList. Una scala è una sequenza di parole che inizia con beginWord, termina con endWord e cambia esattamente una lettera da una parola alla successiva. Ogni parola dopo beginWord deve provenire da wordList.

Restituisci il numero di parole nella scala più breve, contando entrambe le estremità, oppure 0 se non esiste alcuna scala. Per esempio, cold, cord, card è una scala di 3 parole. beginWord non deve necessariamente essere in wordList, ma endWord sì.

Funzione

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

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ù corta, oppure 0 se non ce n’è nessuna

Vincoli

1 ≤ beginWord.length ≤ 10
endWord e ogni parola in wordList ha la stessa lunghezza di beginWord.
1 ≤ wordList.length ≤ 5000
Tutte le parole contengono solo lettere inglesi minuscole.
beginWord != endWord
Le parole in wordList sono tutte diverse. beginWord può essere o meno una di esse.

Esempi

Input: beginWord = "lead"endWord = "gold"wordList = ["load", "goad", "gold", "lend", "lewd", "bold"]
Output: 4
Spiegazione: lead e gold differiscono per tre lettere, quindi nessuna sequenza ha meno di 4 parole, e lead, load, goad, gold ne ha esattamente 4. Anche lend e lewd differiscono da lead per una lettera, ma nessuna delle due porta a una nuova parola, e a bold si può arrivare solo da gold.

Input: beginWord = "cat"endWord = "dog"wordList = ["cot", "cog", "dot", "dig"]
Output: 0
Spiegazione: cat, cot, cog arrivano a una lettera di distanza da dog, ma dog non è nell'elenco, quindi nessuna scala può terminare lì.

Input: beginWord = "ab"endWord = "cd"wordList = ["ab", "cb", "cd", "ad"]
Output: 3
Spiegazione: ab, ad, cd e ab, cb, cd richiedono entrambi 3 parole. ab è anche nell’elenco, ma l’inizio viene conteggiato una sola volta in entrambi i casi.

+14 test nascosti all’invio

Per approfondire

Puoi restituire una delle catene più brevi, con le parole in ordine, e non solo la sua lunghezza?

Suggerimenti

Aprili uno alla volta. Ognuno rivela un po’ di più.

0 di 3 aperti

Soluzione

Considera le parole come nodi di un grafo, con un arco tra due parole che differiscono per una lettera. Una scala è quindi un percorso da beginWord a endWord e ogni arco ha lo stesso costo, quindi la scala più breve è il percorso con il minor numero di archi. La ricerca in ampiezza trova esattamente questo. La difficoltà del problema sta nel trovare rapidamente gli archi: confrontare ogni coppia di 5,000 parole significa fare 25 milioni di confronti, quindi la soluzione migliore cerca i vicini tramite modelli con caratteri jolly. Qui sotto, n è il numero di parole e L la loro lunghezza.

Prova ogni ladder con la ricerca in profondità

Corretto, ma non termina sui test più grandi

Intuizione

Inizia da beginWord. Dalla parola corrente, prova ogni parola non ancora usata che differisce di una lettera e prosegui la ricerca da lì. Quando raggiungi endWord, registra la lunghezza della sequenza se è la più corta trovata finora. Segna come usate le parole del percorso corrente, così una sequenza non torna mai sui propri passi, e libera ogni parola quando fai marcia indietro, in modo che altre sequenze possano usarla. Una volta trovata una sequenza di best parole, smetti di estendere qualsiasi percorso che abbia già best-1 parole: non può essere completato con una lunghezza minore.

È corretto perché prova tutte le sequenze che non ripetono mai una parola, e una sequenza più corta non ripete mai una parola: se una parola comparisse due volte, eliminando la parte tra le due occorrenze si otterrebbe una sequenza più corta.

È lento perché il numero di sequenze cresce enormemente. Considera 26 parole che differiscono solo per la prima lettera, aaa, baa fino a zaa: ogni coppia differisce di una lettera, quindi la ricerca può esplorarle in qualsiasi ordine prima di proseguire, e 26 parole possono essere ordinate in circa 4 × 10^26 modi. Il taglio aiuta solo dopo aver trovato una sequenza. Quando non è possibile raggiungere endWord, non si taglia mai nulla, e una lista di 34 parole è già troppo grande perché la ricerca riesca a terminarla. Inoltre, la ricorsione raggiunge una profondità pari alla lunghezza della sequenza, che può essere di migliaia di parole.

Algoritmo

Contrassegna beginWord come usata se è nell’elenco e imposta best a 0.
Scrivi search(word, length). Se word è endWord, mantieni length quando è inferiore a best, quindi restituisci.
Se best non è 0 e length + 1 ≥ best, restituisci: questo percorso non può vincere.
Per ogni parola non usata che differisce di una lettera da word, contrassegnala come usata, chiama search(next, length + 1), quindi contrassegnala di nuovo come non usata.
Chiama search(beginWord, 1) e restituisci best, che rimane 0 se non esiste alcuna sequenza.

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

Ricerca in ampiezza, confrontando ogni coppia

Corretto, ma non termina sui test più grandi

Intuizione

La ricerca in ampiezza esplora le parole in ordine di distanza. Prima beginWord, una scala di 1 parola. Poi ogni parola che dista una lettera, scale di 2 parole. Poi ogni nuova parola che dista una lettera da quelle, scale di 3 parole, e così via. Una coda mantiene quest’ordine: le parole ne escono nell’ordine in cui sono entrate, quindi tutte le parole a distanza d escono prima di qualsiasi parola a distanza d + 1.

È per questo ordine che la prima scala trovata dalla BFS è la più breve. Quando una parola viene raggiunta per la prima volta a distanza d, tutte le parole più vicine di d sono già state esplorate, quindi, se esistesse una scala più breve per raggiungerla, la ricerca l’avrebbe raggiunta prima. Lo stesso ragionamento rende sicuro contrassegnare una parola come visitata nel momento in cui entra nella coda: la sua distanza è definitiva e raggiungerla di nuovo più tardi può solo richiedere un percorso più lungo. Quindi ogni parola entra nella coda una sola volta e, non appena endWord compare tra le parole vicine, la sua distanza è la risposta.

Questa versione trova le parole vicine confrontandole con ogni parola della lista, lettera per lettera, e fermandosi alla seconda differenza. Per ciascuna delle al più n parole che escono dalla coda, servono n confronti di un massimo di L lettere, quindi il costo totale è O(n² × L). Con 5.000 parole e una ricerca che ne visita la maggior parte, si arriva a 25 milioni di confronti tra parole. Un linguaggio compilato li esegue rapidamente, ma Python impiega diversi secondi con il test più grande.

Algoritmo

Se endWord non è in wordList, restituisci 0.
Inserisci beginWord in una coda con lunghezza 1. Contrassegnalo come visitato se è nell’elenco.
Estrai dalla coda la parola successiva e la sua lunghezza.
Confrontala con ogni parola non visitata nell’elenco. Per ciascuna che differisce di esattamente una lettera: se è endWord, restituisci length + 1; altrimenti contrassegnala come visitata e aggiungila con lunghezza + 1.
Se la coda si svuota, endWord è irraggiungibile: 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 0

Ricerca in ampiezza con bucket jolly

Intuizione

Mantieni la ricerca in ampiezza e rendi economico trovare i vicini. Due parole differiscono esattamente per una lettera quando, nascondendo la stessa posizione in entrambe, diventano uguali: hot e hit diventano entrambe h*t. Assegna quindi a ogni parola L schemi, uno per ogni posizione nascosta, e aggiungi la parola a un contenitore per ogni schema. I vicini di una parola sono le altre parole nei suoi contenitori L, trovate con L ricerche hash invece di scorrere l’intera lista.

Ecco la ricerca sul primo esempio. lead ha gli schemi *ead, l*ad, le*d e lea*. Il contenitore l*ad contiene load e le*d contiene lend e lewd, quindi il livello 2 comprende queste tre parole. Da load, il contenitore *oad fornisce goad al livello 3 e, da goad, go*d fornisce gold al livello 4.

Un altro risparmio: quando il contenitore di una parola è stato esaminato, tutte le parole che contiene sono state raggiunte, quindi svuotalo. Le parole successive che condividono lo schema non troverebbero comunque nulla di nuovo. Nel test in cui aaa, baa fino a zaa condividono *aa, quel contenitore di 26 parole viene esaminato una volta invece di 26 volte. Pertanto, la ricerca legge ciascuna delle n × L voci dei contenitori al massimo una volta.

La creazione degli schemi richiede n × L stringhe di L lettere, tempo e spazio O(n × L²); anche la ricerca ha lo stesso costo: ogni parola estratta dalla coda ricrea i suoi L schemi. Per 5.000 parole di 10 lettere, sono circa 500.000 passaggi sulle lettere, contro un massimo di 250 milioni per il confronto a coppie.

Algoritmo

Se endWord non è in wordList, restituisci 0.
Per ogni parola nell’elenco e per beginWord, aggiungi la parola al contenitore di ciascuno dei suoi schemi L.
Inizia la coda con beginWord, contrassegnalo come visitato e imposta la lunghezza a 1.
Elabora la coda un livello alla volta. Se una parola è endWord, restituisci la lunghezza. Altrimenti, per ciascuno dei suoi schemi, aggiungi al livello successivo ogni parola non visitata in quel contenitore, contrassegnala come visitata e svuota il contenitore.
Dopo ogni livello, aggiungi 1 alla lunghezza. 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

La maggior parte delle risposte sbagliate dipende dal contare la cosa sbagliata o dalla regola relativa a endWord.

Restituire il numero di modifiche invece del numero di parole. Da lead a gold servono 3 modifiche e 4 parole, quindi la risposta è 4.
Non verificare che endWord sia in wordList. Nel secondo esempio, la ricerca ottiene una lettera da dog, ma la risposta è 0.
Usare una ricerca in profondità e restituire la prima sequenza trovata. La DFS segue un ramo fino in fondo, quindi la prima sequenza trovata è spesso lunga.
Contrassegnare una parola come visitata quando esce dalla coda invece che quando vi entra. Una parola in un bucket pieno di 26 elementi può così entrare nella coda fino a 25 volte, e la coda cresce ben oltre n.
Lasciare beginWord senza contrassegnarlo quando è anche in wordList. La ricerca lo raggiunge di nuovo due livelli dopo e ripete il lavoro. Contrassegnalo come visitato fin dall'inizio.
Verificare che le parole differiscano al massimo per una lettera. Ogni parola differisce da se stessa per zero lettere, quindi la condizione è esattamente una.
Ricorrere lungo la sequenza. Un test nascosto ha una sequenza più breve di 1.500 parole, abbastanza lunga da causare un overflow dello stack delle chiamate in alcuni linguaggi. La BFS ha bisogno solo di una coda.

Domande frequenti4

Perché la ricerca in ampiezza trova la catena di parole più breve?

BFS esplora le parole a turni: prima quella iniziale, poi ogni parola a una modifica di distanza, quindi ogni parola a due modifiche di distanza. Una parola viene raggiunta per la prima volta nel turno più precoce in cui è possibile raggiungerla, quindi la sua distanza è il minor numero di modifiche possibile. Questo funziona solo perché ogni modifica ha lo stesso costo. Con costi diversi per ogni passaggio, ti servirebbe invece l'algoritmo di Dijkstra.

Qual è la complessità temporale di Word Ladder?

Con i bucket con caratteri jolly, creare gli schemi ed eseguire la ricerca richiede un tempo O(n × L²) per n parole di lunghezza L, poiché ogni parola ha L schemi di L lettere. Confrontare ogni coppia di parole richiede invece O(n² × L), mentre provare ogni percorso con una ricerca in profondità è esponenziale.

Come trovi le parole che differiscono di una sola lettera?

Un modo consiste nei bucket con caratteri jolly mostrati sopra: le parole che condividono uno schema come h*t sono vicine. L’altro consiste nel sostituire ogni posizione della parola con ciascuna delle 26 lettere e cercare il risultato in un insieme hash delle parole. Questo comporta 26 × L ricerche per parola, ognuna delle quali calcola l’hash di L lettere, quindi O(n × 26 × L²) in totale. Entrambi i metodi sono più efficienti del confronto con l’intero elenco.

La BFS bidirezionale può rendere più veloce Word Ladder?

Sì. Cerca contemporaneamente da beginWord e da endWord, ampliando sempre di un livello il lato più piccolo, e fermati quando una nuova parola è già stata raggiunta dall’altro lato. La sequenza ha quindi una parola in più rispetto alle modifiche effettuate complessivamente su entrambi i lati. Se ogni parola ha circa b vicini e la sequenza richiede d modifiche, una ricerca può visitare circa b^d parole, mentre due ricerche che si incontrano a metà ne visitano circa 2 × b^(d/2).

Python

def ladderLength(beginWord, endWord, wordList):
    # Scrivi il codice qui

Casi di test

Caso 1

Caso 2

Caso 3

Input

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

Atteso

Word Ladder

Funzione

Vincoli

Esempi

Suggerimenti

Soluzione

Prova ogni ladder con la ricerca in profondità

Ricerca in ampiezza, confrontando ogni coppia

Ricerca in ampiezza con bucket jolly

Trappole e casi limite

Domande frequenti4

Problemi simili