Word Ladder
Recibes dos palabras, beginWord y endWord, y una lista de palabras wordList. Una escalera empieza con beginWord, termina con endWord y cambia exactamente una letra de cada palabra a la siguiente. Todas las palabras posteriores a beginWord deben provenir de wordList, así que endWord debe estar en ella; beginWord no tiene por qué estarlo.
Devuelve la cantidad de palabras de la escalera más corta, contando ambos extremos, o 0 si no hay ninguna.
Función
- beginWordstring
- la primera palabra de la escalera
- endWordstring
- la palabra a la que debe llegar la escalera
- wordListstring-array
- las palabras de las que debe partir cada paso posterior
- Devuelveinteger
- el número de palabras de la escalera más corta, o 0 si no hay ninguna
Restricciones
1 ≤ beginWord.length ≤ 10endWordy cada palabra dewordListtienen la misma longitud quebeginWord.1 ≤ wordList.length ≤ 5000- Todas las palabras contienen únicamente letras minúsculas del alfabeto inglés.
beginWord != endWord- Las palabras de
wordListson todas diferentes. Es posible quebeginWordsea una de ellas o que no.
Ejemplos
- Entrada
- beginWord = "lead"endWord = "gold"wordList = ["load", "goad", "gold", "lend", "lewd", "bold"]
- Salida
- 4
- Explicación
leadygolddifieren en tres letras, así que una escalera necesita al menos 4 palabras, ylead,load,goad,goldtiene 4.lendylewdson callejones sin salida.
- Entrada
- beginWord = "cat"endWord = "dog"wordList = ["cot", "cog", "dot", "dig"]
- Salida
- 0
- Explicación
cat,cot,cogestá a una letra dedog, perodogno está en la lista, así que ninguna escalera puede terminar ahí.
- Entrada
- beginWord = "ab"endWord = "cd"wordList = ["ab", "cb", "cd", "ad"]
- Salida
- 3
- Explicación
ab,ad,cdyab,cb,cdcontienen 3 palabras cada uno.abtambién está en la lista, pero el inicio se cuenta una sola vez.
Para ir más allá
¿Puedes devolver una de las escaleras más cortas, con las palabras en orden, en lugar de su longitud?
Pistas
Ábrelas de una en una. Cada una revela un poco más.
Imagina cada palabra como un punto y dibuja una línea entre dos palabras que difieran exactamente en una letra. ¿Qué es una escalera en esa representación y cuál es la más corta?
La escalera más corta es el camino con menos líneas, y todas las líneas cuentan lo mismo. La búsqueda en anchura llega a todas las palabras que están a un paso antes que a cualquier palabra que esté a dos pasos, así que la primera vez que llega a
endWordha usado el menor número de pasos. Marca una palabra como visitada en cuanto llegues a ella por primera vez.Comparar una palabra con la lista completa para encontrar sus vecinas es lento. En su lugar, oculta una letra a la vez:
hot,hatyhitse convierten enh*t. Coloca cada palabra en el grupo de cada uno de sus patrones. Las vecinas de una palabra son las otras palabras de sus grupos. Ejecuta la búsqueda nivel por nivel desdebeginWordy cuenta los niveles.
Solución
Trata las palabras como nodos de un grafo, con una arista entre las palabras que difieren en una letra. Todas las aristas tienen el mismo costo, así que la búsqueda en anchura encuentra la escalera más corta. La parte difícil es encontrar las aristas rápidamente. A continuación, n es el número de palabras y L su longitud.
Prueba cada escalera con búsqueda en profundidad
Correcto, pero no termina con las pruebas más grandes
Intuición
Desde la palabra actual, prueba cada palabra no utilizada que difiera en una letra y explora más a fondo, manteniendo la longitud al llegar a endWord. Marca como utilizadas las palabras del camino y libéralas al retroceder. Una vez que exista una escalera de best palabras, deja de extender los caminos de best-1 palabras.
Esto prueba todas las escaleras sin palabras repetidas, y una escalera más corta nunca repite una palabra: eliminar la parte entre dos copias la acortaría.
Las 26 palabras aaa, baa hasta zaa difieren todas en una letra y se pueden ordenar de aproximadamente 4 × 10^26 maneras. Si no se puede llegar a endWord, el corte nunca se activa y la búsqueda las prueba todas.
Algoritmo
- Marca que
beginWordse ha usado si está en la lista, y establecebesten 0. search(word, length): al llegar aendWord, conservalengthsi superabest, y retorna. Sibestestá establecido ylength + 1 ≥ best, retorna.- De lo contrario, para cada palabra no usada que esté a una letra de distancia, márcala, llama a
search(next, length + 1)y desmárcala. - Retorna
bestdespués desearch(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 bestBúsqueda en anchura, comparando cada par
Correcto, pero no termina con las pruebas más grandes
Intuición
Una cola explora las palabras en orden de distancia: todas las palabras a distancia d salen de ella antes que cualquier palabra a distancia d + 1. Así que, cuando se alcanza una palabra por primera vez a distancia d, ya se han explorado todas las palabras más cercanas, y una escalera más corta hasta ella la habría alcanzado antes. Su distancia queda fijada en el momento en que se incorpora a la cola, así que márcala como visitada entonces, y la primera vez que aparece endWord, su distancia es la respuesta.
Esta versión encuentra las palabras vecinas comparándola con todas las palabras de la lista, y se detiene al encontrar la segunda diferencia: O(n² × L), hasta 25 millones de comparaciones de palabras para 5,000 palabras.
Algoritmo
- Si
endWordno está enwordList, devuelve 0. - Encola
beginWordcon longitud 1, marcado como visitado si está en la lista. - Toma la siguiente palabra y compárala con cada palabra no visitada. Por cada palabra que difiera en una letra: si es
endWord, devuelve longitud + 1; de lo contrario, márcala y encola con longitud + 1. - Si la cola se queda vacía, devuelve 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 0Búsqueda en anchura con grupos de comodines
Intuición
Dos palabras difieren exactamente en una letra cuando, al ocultar la misma posición, se vuelven iguales: hot y hit se convierten en h*t. Genera L patrones para cada palabra, uno por cada posición oculta, y añádela a un grupo para cada patrón. Las palabras vecinas de una palabra son las demás palabras de sus grupos de L, que se encuentran mediante L búsquedas hash en lugar de recorrer toda la lista.
En el primer ejemplo, l*ad contiene load y le*d contiene lend y lewd, así que el nivel 2 está formado por esas tres palabras; *oad da después goad, y go*d da gold en el nivel 4.
Una vez que se recorre un grupo, se llega a todas las palabras que contiene, así que vacíalo: el grupo de 26 palabras *aa se recorre una vez, no 26 veces. El costo es de O(n × L²) en tiempo y espacio, aproximadamente 500,000 pasos de letras para 5,000 palabras de 10 letras.
Algoritmo
- Si
endWordno está enwordList, devuelve 0. - Agrupa cada palabra, incluida
beginWord, en cada uno de sus patronesL. - Encola
beginWord, marcado como visitado, con longitud 1. - Para cada palabra de un nivel: si es
endWord, devuelve la longitud. De lo contrario, mueve cada palabra no visitada de cada uno de sus grupos de patrones al siguiente nivel, márcala como visitada y vacía el grupo. - Suma 1 a la longitud por cada nivel. Si la cola se queda vacía, devuelve 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
Errores comunes y casos límite
- Contar los cambios en lugar de las palabras. De
leadagoldhay 3 cambios y 4 palabras; la respuesta es 4. - Omitir la comprobación de que
endWordesté enwordList. El segundo ejemplo llega acog, que está a una letra dedog, pero la respuesta es 0. - Marcar una palabra como visitada cuando sale de la cola. Una palabra del grupo
*aapuede entonces añadirse hasta 25 veces, y la cola crece mucho más allá den. - Recorrer la escalera mediante recursión. Una escalera más corta puede tener miles de palabras, suficientes para desbordar la pila de llamadas.
Preguntas frecuentes3
¿Cuál es la complejidad temporal de Word Ladder?
Con los buckets comodín, el costo es O(n × L²) para n palabras de longitud L: cada palabra tiene L patrones de L letras. Comparar cada par de palabras cuesta O(n² × L), y probar cada escalera con búsqueda en profundidad es exponencial.
¿Cómo encuentras las palabras que están a una letra de distancia?
Los grupos comodín son una forma. La otra es cambiar cada posición por cada una de las 26 letras y buscar el resultado en un conjunto hash de palabras: 26 × L búsquedas de L letras por palabra, O(n × 26 × L²) en total. Ambas opciones son más eficientes que recorrer la lista.
¿Puede la búsqueda en anchura bidireccional hacer que Word Ladder sea más rápido?
Sí. Busca desde ambos extremos a la vez, ampliando siempre el lado más pequeño en un nivel, y detente cuando ambos lados se encuentren. Con aproximadamente b vecinos por palabra y d cambios, una búsqueda puede recorrer aproximadamente b^d palabras; dos búsquedas que se encuentran en el medio recorren aproximadamente 2 × b^(d/2).
Problemas similares
Problemas que usan las mismas ideas. Resolver dos o tres es lo que fija un patrón.
def ladderLength(beginWord, endWord, wordList):
# Escribe el código aquíPrueba #1
Prueba #2
Prueba #3
Argumentos
beginWord = "lead" endWord = "gold" wordList = ["load", "goad", "gold", "lend", "lewd", "bold"]
Salida Esperada
4