Word Ladder

Q: ¿Puede la búsqueda bidireccional en anchura hacer que Word Ladder sea más rápido?

Sí. Busca desde beginWord y desde endWord a la vez, haciendo crecer siempre el lado más pequeño un nivel, y detente cuando el otro lado ya haya alcanzado una palabra nueva. La escalera tiene entonces una palabra más que los cambios realizados en ambos lados en conjunto. Si cada palabra tiene aproximadamente b vecinas y la escalera requiere d cambios, una búsqueda puede abarcar aproximadamente b^d palabras, mientras que dos búsquedas que se encuentran en el medio abarcan aproximadamente 2 × b^(d/2) .

DifícilGrafos Cola

+10

Se te dan dos palabras, beginWord y endWord, y una lista de palabras wordList. Una escalera es una secuencia de palabras que comienza con beginWord, termina con endWord y cambia exactamente una letra de cada palabra a la siguiente. Todas las palabras después de beginWord deben provenir de wordList.

Devuelve el número de palabras de la escalera más corta, contando ambos extremos, o 0 si no existe ninguna escalera. Por ejemplo, cold, cord, card es una escalera de 3 palabras. beginWord no tiene que estar en wordList, pero endWord sí.

Función

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

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 provenir cada paso posterior
Devuelveinteger: el número de palabras en la escalera más corta, o 0 si no hay ninguna

Restricciones

1 ≤ beginWord.length ≤ 10
endWord y cada palabra de wordList tienen la misma longitud que beginWord.
1 ≤ wordList.length ≤ 5000
Todas las palabras contienen únicamente letras minúsculas del alfabeto inglés.
beginWord != endWord
Las palabras de wordList son todas diferentes. beginWord puede ser una de ellas o no.

Ejemplos

Entrada: beginWord = "lead"endWord = "gold"wordList = ["load", "goad", "gold", "lend", "lewd", "bold"]
Salida: 4
Explicación: lead y gold difieren en tres letras, así que ninguna escalera tiene menos de 4 palabras, y lead, load, goad, gold tiene exactamente 4. lend y lewd también difieren en una letra de lead, pero ninguna lleva a un lugar nuevo, y solo se puede llegar a bold desde gold.

Entrada: beginWord = "cat"endWord = "dog"wordList = ["cot", "cog", "dot", "dig"]
Salida: 0
Explicación: cat, cot, cog queda a una letra de dog, pero dog no 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, cd y ab, cb, cd tienen 3 palabras. ab también está en la lista, pero el inicio se cuenta una sola vez en cualquier caso.

+14 pruebas ocultas al enviar

Para ir más allá

¿Puedes devolver una de las escaleras más cortas, con las palabras en orden, y no solo su longitud?

Pistas

Ábrelas de una en una. Cada una revela un poco más.

0 de 3 abiertas

Solución

Considera las palabras como los nodos de un grafo, con una arista entre dos palabras que difieren en una letra. Una escalera es, entonces, un camino desde beginWord hasta endWord, y todas las aristas tienen el mismo coste, así que la escalera más corta es el camino con menos aristas. La búsqueda en anchura encuentra exactamente eso. Lo que hace que el problema sea difícil es encontrar las aristas rápidamente: comparar cada par de 5,000 palabras supone 25 millones de comparaciones, así que la mejor solución busca las palabras vecinas mediante patrones comodín. 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

Empieza en beginWord. Desde la palabra actual, prueba cada palabra sin usar que esté a una letra de distancia y profundiza a partir de ella. Cuando llegues a endWord, registra la longitud de la escalera si es la más corta hasta el momento. Marca como usadas las palabras de la ruta actual para que una escalera nunca vuelva sobre sí misma, y libera cada palabra al retroceder para que otras escaleras puedan usarla. Una vez que tengas una escalera de best palabras, deja de extender cualquier ruta que ya tenga best-1 palabras: no puede terminar siendo más corta.

Esto es correcto porque prueba todas las escaleras que nunca repiten una palabra, y una escalera más corta nunca repite ninguna: si una palabra apareciera dos veces, eliminar la parte entre las dos copias daría una escalera más corta.

Es lento porque la cantidad de escaleras se dispara. Toma 26 palabras que solo difieren en su primera letra, aaa, baa hasta zaa: cada par está a una letra de distancia, así que la búsqueda puede recorrerlas en cualquier orden antes de continuar, y las 26 palabras se pueden ordenar de aproximadamente 4 × 10^26 maneras. El recorte solo ayuda una vez que se encuentra alguna escalera. Cuando no se puede llegar a endWord, nunca se recorta nada, y una lista de 34 palabras ya supera lo que la búsqueda puede completar. La recursión también alcanza una profundidad igual a la de la escalera, que puede tener miles de palabras.

Algoritmo

Marca beginWord como usado si está en la lista y establece best en 0.
Escribe search(word, length). Si word es endWord, conserva length si supera a best y retorna.
Si best no es 0 y length + 1 ≥ best, retorna: este camino no puede ganar.
Para cada palabra no usada que esté a una letra de word, márcala como usada, llama a search(next, length + 1) y después desmárcala.
Llama a search(beginWord, 1) y retorna best, que permanece en 0 si no existe ninguna secuencia.

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

Búsqueda en anchura, comparando cada par

Correcto, pero no termina con las pruebas más grandes

Intuición

La búsqueda en anchura explora las palabras por orden de distancia. Primero, beginWord, una escalera de 1 palabra. Después, cada palabra que está a una letra de distancia, escaleras de 2. Después, cada palabra nueva que está a una letra de distancia de esas, escaleras de 3, y así sucesivamente. Una cola mantiene ese orden: las palabras salen de ella en el orden en que se añadieron, así que todas las palabras a distancia d salen antes que cualquier palabra a distancia d + 1.

Ese orden explica por qué la primera escalera que encuentra BFS es la más corta. Cuando se alcanza por primera vez una palabra a distancia d, ya se han explorado todas las palabras que están a una distancia menor que d; por tanto, si existiera una escalera más corta hasta ella, la búsqueda habría llegado antes a esa palabra. El mismo razonamiento permite marcar una palabra como visitada en el momento en que se añade a la cola: su distancia ya es definitiva, y volver a alcanzarla más tarde solo puede dar una distancia mayor. Así, cada palabra se añade a la cola una sola vez y, en cuanto endWord aparece como vecina, su distancia es la respuesta.

Esta versión encuentra las vecinas de una palabra comparándola con cada palabra de la lista, letra por letra, y se detiene al encontrar la segunda diferencia. Cada una de las hasta n palabras que salen de la cola requiere n comparaciones de hasta L letras, es decir, O(n² × L) en total. Con 5.000 palabras y una búsqueda que visita la mayoría de ellas, eso supone hasta 25 millones de comparaciones entre palabras. Un lenguaje compilado puede hacerlo rápidamente, pero Python necesita varios segundos en la prueba más grande.

Algoritmo

Si endWord no está en wordList, devuelve 0.
Pon beginWord en una cola con longitud 1. Márcala como visitada si está en la lista.
Toma la siguiente palabra y su longitud de la cola.
Compárala con cada palabra no visitada de la lista. Por cada una que esté a una sola letra de distancia: si es endWord, devuelve longitud + 1; de lo contrario, márcala como visitada y añádela con longitud + 1.
Si la cola se vacía, no se puede llegar a endWord: 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 0

Búsqueda en anchura con cubetas comodín

Intuición

Mantén la búsqueda en anchura y haz que encontrar vecinos sea barato. Dos palabras están separadas por exactamente una letra cuando, al ocultar la misma posición en ambas, se vuelven iguales: hot y hit se convierten en h*t. Así que dale a cada palabra L patrones, uno por cada posición oculta, y añade la palabra a un cubo para cada patrón. Los vecinos de una palabra son las otras palabras en sus L cubos, que se encuentran mediante L búsquedas hash en lugar de recorrer toda la lista.

Así funciona la búsqueda en el primer ejemplo. lead tiene los patrones *ead, l*ad, le*d y lea*. El cubo l*ad contiene load y el cubo le*d contiene lend y lewd, así que el nivel 2 contiene esas tres palabras. Desde load, el cubo *oad da goad en el nivel 3 y, desde goad, go*d da gold en el nivel 4.

Un ahorro más: cuando se ha recorrido el cubo de una palabra, ya se ha llegado a todas las palabras que contiene, así que vacíalo. Las palabras posteriores que compartan el patrón no encontrarían nada nuevo allí de todos modos. En la prueba en la que aaa, baa hasta zaa comparten *aa, ese cubo de 26 palabras se recorre una sola vez, en lugar de 26. Así, la búsqueda lee cada entrada de los cubos n × L como máximo una vez.

Crear los patrones requiere n × L cadenas de L letras, tiempo y espacio O(n × L²), y la búsqueda cuesta lo mismo: cada palabra que sale de la cola vuelve a generar sus L patrones. Para 5.000 palabras de 10 letras, eso supone unos 500.000 pasos de letras, frente a hasta 250 millones para la comparación por pares.

Algoritmo

Si endWord no está en wordList, devuelve 0.
Para cada palabra de la lista y para beginWord, agrega la palabra al grupo de cada uno de sus patrones L.
Inicia la cola con beginWord, márcala como visitada y establece la longitud en 1.
Procesa la cola un nivel a la vez. Si una palabra es endWord, devuelve la longitud. De lo contrario, para cada uno de sus patrones, agrega al siguiente nivel todas las palabras no visitadas de ese grupo, márcalas como visitadas y vacía el grupo.
Después de cada nivel, suma 1 a la longitud. 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

La mayoría de las respuestas incorrectas se deben a contar lo que no corresponde o a la regla sobre endWord.

Devolver el número de cambios en vez del número de palabras. De lead a gold se necesitan 3 cambios y 4 palabras, y la respuesta es 4.
No comprobar que endWord esté en wordList. En el segundo ejemplo, la búsqueda obtiene una letra de dog, pero la respuesta es 0.
Usar búsqueda en profundidad y devolver la primera escalera que encuentra. La búsqueda en profundidad sigue una rama hasta el final, así que la primera escalera suele ser larga.
Marcar una palabra como visitada cuando sale de la cola en vez de cuando se agrega a ella. Una palabra de un grupo completo de 26 puede agregarse a la cola hasta 25 veces, y esta crece mucho más allá de n.
Dejar beginWord sin marcar cuando también está en wordList. La búsqueda vuelve a alcanzarla dos niveles después y repite trabajo. Márcala como visitada desde el principio.
Comprobar si las palabras difieren en como máximo una letra. Todas las palabras difieren de sí mismas en cero letras, así que la condición debe ser exactamente una.
Usar recursión a lo largo de la escalera. Una prueba oculta tiene una escalera más corta de 1,500 palabras, lo bastante profunda como para desbordar la pila de llamadas en algunos lenguajes. BFS solo necesita una cola.

Preguntas frecuentes4

¿Por qué la búsqueda en anchura encuentra la escalera de palabras más corta?

BFS explora las palabras por rondas: primero la palabra inicial, después todas las palabras a un cambio de distancia y luego todas las palabras a dos cambios de distancia. Se llega a una palabra por primera vez en la ronda más temprana que puede alcanzarla, así que su distancia es el menor número posible de cambios. Esto solo funciona porque cada cambio cuenta lo mismo. Si los pasos tuvieran costos diferentes, necesitarías usar el algoritmo de Dijkstra.

¿Cuál es la complejidad temporal de Word Ladder?

Con los buckets comodín, crear los patrones y realizar la búsqueda lleva un tiempo de O(n × L²) para n palabras de longitud L, ya que cada palabra tiene L patrones de L letras. Comparar cada par de palabras cuesta O(n² × L), y probar cada escalera con una búsqueda en profundidad es exponencial.

¿Cómo encuentras las palabras que están a una letra de distancia?

Una forma es usar los grupos con comodines de arriba: las palabras que comparten un patrón, como h*t, son vecinas. La otra es cambiar cada posición de la palabra por cada una de las 26 letras y buscar el resultado en un conjunto hash de las palabras. Eso cuesta 26 × L búsquedas por palabra, cada una calculando el hash de L letras, es decir, O(n × 26 × L²) en total. Ambas opciones son mejores que comparar con toda la lista.

¿Puede la búsqueda bidireccional en anchura hacer que Word Ladder sea más rápido?

Sí. Busca desde beginWord y desde endWord a la vez, haciendo crecer siempre el lado más pequeño un nivel, y detente cuando el otro lado ya haya alcanzado una palabra nueva. La escalera tiene entonces una palabra más que los cambios realizados en ambos lados en conjunto. Si cada palabra tiene aproximadamente b vecinas y la escalera requiere d cambios, una búsqueda puede abarcar aproximadamente b^d palabras, mientras que dos búsquedas que se encuentran en el medio abarcan aproximadamente 2 × b^(d/2).

Python

def ladderLength(beginWord, endWord, wordList):
    # Escribe el código aquí

Casos de prueba

Caso 1

Caso 2

Caso 3

Entrada

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

Esperado

Word Ladder

Función

Restricciones

Ejemplos

Pistas

Solución

Prueba cada escalera con búsqueda en profundidad

Búsqueda en anchura, comparando cada par

Búsqueda en anchura con cubetas comodín

Errores comunes y casos límite

Preguntas frecuentes4

Problemas similares