Entrevista de código: ¿cómo resolver Word Ladder con BFS bidireccional?

Enunciado y contexto aplicable

Dados beginWord, endWord y wordList, encuentra la longitud de la secuencia de transformación más corta. Cada par adyacente debe diferir en exactamente una posición, y cada palabra posterior a beginWord, incluida endWord, debe aparecer en el diccionario. La longitud devuelta cuenta palabras, no cambios.

beginWord = "hit"
endWord   = "cog"
wordList  = ["hot", "dot", "dog", "lot", "log", "cog"]

One shortest sequence:
hit -> hot -> dot -> dog -> cog

Return: 5

Utiliza el contrato estándar: beginWord y endWord son distintas, todas las palabras contienen letras inglesas en minúsculas, cada palabra del diccionario tiene la misma longitud L, las entradas del diccionario son únicas y hay como máximo N = 5,000 entradas. Si endWord está ausente o es inalcanzable, devuelve 0.

Este es un problema de grafos cuyo grafo está oculto dentro de cadenas de texto. Cada palabra válida es un vértice; dos palabras comparten una arista no dirigida de costo unitario cuando difieren en una posición. Por lo tanto, el enunciado solicita el camino más corto entre un único par de nodos en un grafo no ponderado. El material público de entrevistas sobre grafos en 2026 todavía clasifica Word Ladder como un problema de transformación mediante BFS, y un relato público de una entrevista de junio de 2026 analiza la variante más compleja Word Ladder II. Esos registros establecen un valor de preparación actual; no establecen una frecuencia de entrevista ni una atribución verificada a una empresa, por lo que este artículo no afirma ninguna de las dos cosas.

Qué evalúa el entrevistador

La primera señal es si el candidato visualiza un grafo implícito. Comparar cada par de palabras del diccionario construye el grafo correcto, pero cuesta O(N²L) comparaciones de caracteres. Una respuesta más sólida genera únicamente los posibles vecinos de la palabra actual: reemplaza cada uno de sus L caracteres con las otras 25 letras y luego utiliza un conjunto hash para verificar la pertenencia al diccionario.

La segunda señal es el argumento del camino más corto. Cada transformación cuesta un paso, por lo que BFS explora los estados en orden de distancia no decreciente. DFS eventualmente podría encontrar un camino, pero no garantiza que el primer camino sea el más corto. Dijkstra es correcto con pesos unitarios, pero añade una cola de prioridad sin aportar información adicional.

La tercera señal es el momento en que se marcan los nodos como visitados. Una palabra debe salir del conjunto de no visitados cuando entra a una frontera, no cuando se expande posteriormente. Un marcado tardío permite que múltiples nodos padre encolen la misma palabra, aumentando tanto el trabajo como la memoria. Con BFS bidireccional, un vecino generado debe verificarse contra la frontera opuesta actual antes de verificarse contra el conjunto de no visitados.

La cuarta señal es si la optimización sigue siendo demostrable. BFS bidireccional mantiene una frontera de nivel completo desde cada extremo y expande la frontera más pequeña. A menudo reduce una búsqueda de tipo árbol de aproximadamente b^d estados a dos búsquedas cercanas a b^(d/2), donde b es el factor de ramificación efectivo y d es la respuesta en número de aristas. No mejora el límite asintótico en el peor de los casos: un diccionario adversario aún puede obligar al algoritmo a inspeccionar casi todas las palabras.

Finalmente, una respuesta sólida expone el costo real de manipulación de cadenas. Cada palabra expandida prueba como máximo 25L mutaciones. En Python, crear una cadena candidata cuesta O(L), por lo que la implementación toma un tiempo esperado de O(NL²) para un alfabeto fijo de 26 letras, con un almacenamiento de O(NL) caracteres. Llamarlo O(NL) asume implícitamente que la construcción de cadenas toma tiempo constante.

Preguntas aclaratorias antes de responder

• ¿Qué cuenta exactamente el valor de retorno? Este contrato cuenta ambos extremos. Una transformación

válida directa devuelve por tanto 2; una API que cuente aristas devolvería uno menos.

• ¿Debe estar endWord en el diccionario? Sí. Si está ausente, devuelve 0 antes de iniciar la búsqueda. Una variante

que permita que el objetivo esté fuera del diccionario cambia esta regla de salida temprana.

• ¿Tienen todas las palabras la misma longitud y el mismo alfabeto? Sí: longitud L, letras inglesas en minúsculas. Unicode,

longitudes mixtas o un alfabeto más grande alteran la generación de vecinos y su costo.

• ¿Son únicas las entradas? Sí. Convertir la entrada a un conjunto sigue siendo útil para verificaciones de

pertenencia y eliminaciones de visitados en tiempo constante esperado. Si se permitieran duplicados, no crearían vértices distintos.

• ¿Necesitamos una longitud, un camino o todos los caminos más cortos? El problema base solo requiere la longitud.

Devolver un camino requiere mapas de nodos padre; devolver todos los caminos más cortos requiere preservar todos los nodos padre del mismo nivel de BFS y no puede usar la misma regla de eliminación inmediata sin modificaciones.

• ¿Es una sola consulta o muchas consultas sobre un diccionario estable? Para una sola consulta, la mutación bajo

demanda es simple y evita construir un índice completo. Las consultas repetidas pueden justificar un índice reutilizable con patrones de comodines.

• ¿Puede beginWord aparecer ya en el diccionario? Sí. Sigue siendo un único vértice y debe eliminarse

del conjunto de no visitados durante la inicialización.

Estructura de respuesta en 30 segundos

“Modelo cada palabra como un vértice y conecto dos palabras cuando difieren en una posición. Cada arista cuesta una transformación, por lo que este es un problema de camino más corto no ponderado. Ejecutaría un BFS bidireccional desde beginWord y endWord, expandiendo siempre la frontera de nivel completo que sea más pequeña. Para cada palabra de la frontera, genero sus como máximo 25L mutaciones de una sola letra y las verifico en un conjunto hash. Si una mutación está en la frontera opuesta, los dos prefijos explorados más cortos forman la secuencia más corta, por lo que devuelvo el conteo de palabras actual más uno. De lo contrario, elimino una palabra válida no vista tan pronto como la agrego a la siguiente frontera. Si endWord está ausente o una frontera queda vacía, devuelvo cero. El peor caso aún visita N palabras; debido a que la construcción de candidatas en Python copia L caracteres, el tiempo es O(NL²) y el contenido de cadenas almacenado es O(NL). Probaría casos directos, inalcanzables, cíclicos, con descubrimientos duplicados y con fronteras asimétricas.”

Análisis detallado paso a paso

Comencemos con el modelo de grafos. Sea el conjunto de vértices todas las palabras del diccionario más beginWord. Para cualesquiera dos palabras de la misma longitud, se añade una arista exactamente cuando su distancia de Hamming es uno. El grafo es no dirigido: si hot puede transformarse en dot, el cambio inverso también es válido. No es ponderado porque cada cambio válido aporta una arista.

Un grafo explícito por pares compara O(N²) pares y gasta O(L) por comparación. Eso representa O(N²L) de preprocesamiento incluso cuando la mayoría de los pares no están relacionados. El alfabeto de entrada ofrece un espacio de candidatas más pequeño. Una palabra tiene a lo sumo 25L mutaciones distintas de una sola letra; la pertenencia al diccionario determina cuáles son vértices reales.

El BFS unidireccional ya es correcto. Su invariante es:

At the start of level k:
  the frontier contains exactly the discovered words at edge distance k;
  no undiscovered word has distance less than k;
  every word outside unvisited has already been assigned its minimum distance.

BFS crea el nivel k + 1 únicamente a partir del nivel k. Por lo tanto, el primer descubrimiento de una palabra utiliza el camino más corto. Eliminar una palabra de unvisited en el momento de su descubrimiento preserva ese hecho y evita entradas duplicadas en la frontera.

Para un único objetivo conocido, se busca desde ambos extremos. front es un nivel completo desde el lado inicial, y back es un nivel completo desde el lado final. sequence_length es igual a la suma de sus profundidades de aristas actuales más uno, porque cuenta las palabras frontera en ambos extremos sin una arista de conexión todavía. Expandir cualquiera de las fronteras completas incrementa esa suma de profundidades en uno. Si una palabra generada pertenece a la frontera opuesta, la arista conectora hace que la respuesta sea sequence_length + 1.

Expandir la frontera más pequeña cambia el rendimiento, no la corrección. Intercambiar los dos conjuntos solo cambia cuál capa válida de BFS avanza a continuación; cada conjunto sigue representando una profundidad exacta desde su propio origen. Verificar la intersección contra la frontera opuesta actual es fundamental. Un único conjunto global unvisited es seguro porque cuando un lado descubre una palabra, la reclama de inmediato. Si una expansión posterior tuviera una arista hacia una capa ya expandida de la otra búsqueda, esa expansión anterior habría descubierto la misma palabra primero, por lo que las búsquedas no pueden cruzarse silenciosamente detrás de sus fronteras actuales.

ALPHABET = "abcdefghijklmnopqrstuvwxyz"


def ladder_length(
    begin_word: str,
    end_word: str,
    word_list: list[str],
) -> int:
    unvisited = set(word_list)
    if end_word not in unvisited:
        return 0

    front = {begin_word}
    back = {end_word}
    unvisited.discard(begin_word)
    unvisited.remove(end_word)
    sequence_length = 1

    while front and back:
        if len(front) > len(back):
            front, back = back, front

        next_front: set[str] = set()

        for word in front:
            for index, original in enumerate(word):
                for letter in ALPHABET:
                    if letter == original:
                        continue

                    candidate = word[:index] + letter + word[index + 1 :]

                    if candidate in back:
                        return sequence_length + 1

                    if candidate in unvisited:
                        unvisited.remove(candidate)
                        next_front.add(candidate)

        front = next_front
        sequence_length += 1

    return 0

Traza el ejemplo mediante capas de frontera:

El algoritmo expande el lado más pequeño cog en la expansión 3. En la expansión 4, dot alcanza a dog o lot alcanza a log, por lo que devuelve 5. El orden de iteración del conjunto puede elegir una arista de encuentro más corta diferente; la longitud no cambia.

Sea N el tamaño del diccionario y L la longitud de las palabras. Cada palabra se agrega a una frontera a lo sumo una vez y, si se expande, prueba 25L candidatas. La búsqueda hash es de O(1) esperado, pero cada candidata por segmentación y concatenación en Python cuesta O(L), dando un tiempo en el peor de los casos esperado de O(NL²) con un alfabeto fijo. Los conjuntos almacenan a lo sumo O(N) referencias y sus cadenas contienen O(NL) caracteres. Las cadenas candidatas temporales añaden O(L) a la vez. Si en una entrevista se utiliza un búfer de caracteres mutable de ancho fijo y se trata la materialización o el hashing de una candidata como O(L), se sigue aplicando el mismo límite riguroso.

Un índice de comodines es la alternativa principal. Asocia patrones como h*t, *ot y ho* con las palabras correspondientes. Puede reutilizarse a lo largo de muchas consultas y evita probar letras ausentes en el diccionario. En Python, crear L cadenas de patrones para N palabras también cuesta O(NL²) de trabajo en caracteres y puede retener O(NL) entradas en los contenedores. Durante el BFS, limpia el contenedor de un patrón consumido o márcalo como procesado; escanear el mismo contenedor grande para muchas palabras puede, de lo contrario, recrear un trabajo cuadrático. Para una sola consulta bajo las restricciones indicadas, la mutación más un conjunto tiene menos partes móviles.

Prueba el contrato ejecutable, no solo el ejemplo:

cases = [
    (
        "hit",
        "cog",
        ["hot", "dot", "dog", "lot", "log", "cog"],
        5,
    ),
    ("hit", "cog", ["hot", "dot", "dog", "lot", "log"], 0),
    ("a", "c", ["a", "b", "c"], 2),
    ("red", "tax", ["ted", "tex", "red", "tax", "tad", "den", "rex", "pee"], 4),
    ("aaa", "bbb", ["aab", "abb", "bbb", "aba", "baa"], 4),
]

for begin_word, end_word, words, expected in cases:
    actual = ladder_length(begin_word, end_word, words)
    assert actual == expected, (begin_word, end_word, actual, expected)

Las pruebas basadas en propiedades pueden generar un diccionario aleatorio pequeño, construir el grafo explícito por pares como un oráculo confiable y comparar su resultado de BFS ordinario con la función optimizada. Mantén también la lista de entrada sin modificaciones, prueba diccionarios donde una frontera crezca mucho más rápido que la otra y confirma que una palabra alcanzable a través de varios nodos padre se expanda solo una vez.

Ejemplo de respuesta de alta calidad

“Las palabras forman un grafo no dirigido implícito. Un vértice es una palabra válida y una arista une palabras con distancia de Hamming uno. Dado que todas las aristas cuestan uno, BFS proporciona el número mínimo de transformaciones. Devolveré el número de palabras, por lo que hit -> hot tiene longitud dos.

Primero coloco el diccionario en un conjunto y descarto el caso en el que endWord esté ausente. Mantengo una frontera en cada extremo y un conjunto de palabras que ninguna de las dos búsquedas ha descubierto. En cada iteración expando la frontera completa más pequeña. Para cada palabra y posición de carácter, pruebo las otras 25 letras minúsculas. Verifico una candidata contra la frontera opuesta primero; una coincidencia conecta dos prefijos de BFS, por lo que la respuesta es el conteo acumulado de palabras más uno. De lo contrario, si la candidata no ha sido visitada, la elimino inmediatamente y la añado a la siguiente frontera.

El invariante es que cada frontera está exactamente a una capa de distancia de su extremo, y cada palabra eliminada ya tiene su distancia mínima respecto al lado que la descubrió. Expandir el lado más pequeño no altera esas capas. La primera conexión entre fronteras es la más corta porque cualquier camino más corto habría conectado dos capas anteriores. La eliminación inmediata evita descubrimientos duplicados.

Se expanden como máximo N palabras. Cada una prueba 25L mutaciones, y Python gasta O(L) en construir cada candidata, por lo que establezco O(NL²) de tiempo esperado y O(NL) de caracteres almacenados. La búsqueda bidireccional usualmente reduce los estados explorados, pero mantiene el mismo peor caso. Para consultas repetidas consideraría un índice de comodines reutilizable; para esta consulta única, la mutación es más simple. Verificaría el ejemplo oficial, objetivo inexistente, transformación directa, múltiples rutas más cortas, ciclos y un oráculo con grafo explícito aleatorio.”

Errores comunes

• Ejecutar DFS y devolver su primer camino → DFS no visita los caminos en orden de conteo de transformaciones →

Usa BFS porque cada arista tiene costo unitario.

• Comparar cada par del diccionario → la construcción del grafo cuesta O(N²L) → **Genera como máximo 25L

vecinos candidatos por cada palabra expandida.**

• Marcar una palabra como visitada solo al extraerla → múltiples nodos padre pueden encolarla → **Elimínala de

unvisited al agregarla a una frontera.**

• Verificar solo unvisited antes de la frontera opuesta → la palabra de encuentro ya habrá sido eliminada

por la otra búsqueda → Prueba primero contra la frontera opuesta actual.

• Expandir siempre el lado llamado front → un lado puede explotar mientras el otro se mantiene pequeño →

Intercambia y expande la frontera de nivel completo más pequeña.

• Confundir el conteo de aristas con el conteo de palabras → el ejemplo devuelve cuatro en lugar de cinco → **Inicializa el

conteo de la secuencia en uno y suma la palabra de conexión en una arista de encuentro.**

• Afirmar que BFS bidireccional cambia la complejidad en el peor de los casos → un diccionario adversario denso aún

puede exponer casi todas las palabras → Describe el beneficio del factor de ramificación como típico, no garantizado.

• Llamar a la mutación en Python O(NL) → cada candidata copia o aplica hash a L caracteres → **Declara el

modelo de operaciones de cadenas y usa O(NL²) para esta implementación.**

• Reutilizar contenedores de comodines sin consumirlos → se escanea repetidamente la misma lista grande →

Limpia cada contenedor de patrones procesado o márcalo como consumido.

• Usar un único conjunto global de visitados pero permitir expansiones de nivel parcial → el orden de encuentro y el cálculo

de la distancia se vuelven difíciles de demostrar → Avanza un nivel de frontera completo a la vez.

• Citar una experiencia de empresa autoreportada como atribución verificada → una publicación pública no es un

registro del empleador → Mantén companyName nulo y usa el registro solo como evidencia pública actual.

Preguntas de seguimiento y cómo abordarlas

Pregunta de seguimiento 1: ¿Cómo devolverías una secuencia más corta real?

Mantén un mapa de nodos padre para cada dirección. Cuando se descubra una candidata, registra la palabra que la produjo. En la arista de encuentro, recorre el mapa de padres del lado inicial hacia atrás hasta beginWord, invierte ese prefijo y luego recorre el mapa de padres del lado final hacia endWord. Dado que la implementación puede intercambiar variables de frontera, almacena los mapas de padres por dirección semántica en lugar de asumir que la variable actual front es siempre el lado inicial. El almacenamiento de padres requiere O(N) referencias además de las cadenas del diccionario.

Pregunta de seguimiento 2: ¿Qué cambia para Word Ladder II, que devuelve todas las secuencias más cortas?

Un solo padre por palabra es insuficiente. Un BFS ordinario por niveles suele ser más fácil de razonar: recolecta cada predecesor que alcance una palabra en su nivel mínimo y elimina las palabras recién descubiertas del diccionario global solo después de que termine el nivel completo. Eso permite múltiples padres en el mismo nivel sin permitir que caminos más largos agreguen padres más tarde. Detente tras completar el primer nivel que alcance a endWord, luego haz backtracking a través del DAG de predecesores. El tamaño de la salida puede ser exponencial, por lo que la complejidad debe incluir el número total y la longitud de las secuencias devueltas.

Pregunta de seguimiento 3: ¿Cuándo es preferible un BFS unidireccional ordinario?

Úsalo cuando el diccionario sea pequeño, solo se conozca un extremo, el grafo sea dirigido y los vecinos inversos sean costosos de obtener, o la simplicidad del código importe más que reducir la frontera. El BFS unidireccional tiene menos invariantes y simplifica la reconstrucción de padres. Mantiene el mismo generador de vecinos y el mismo límite O(NL²) para esta representación en Python.

Pregunta de seguimiento 4: ¿Cuándo construirías contenedores de patrones con comodines?

Constrúyelos cuando muchas consultas compartan un diccionario estable, el alfabeto sea grande o generar cada sustitución del alfabeto desperdicie trabajo. Asigna una versión al índice junto con el diccionario, incluye beginWord patrones por consulta cuando no esté indexado y consume cada contenedor como máximo una vez por búsqueda. La compensación radica en el tiempo de preprocesamiento, la memoria de los contenedores y la invalidación cuando cambian las palabras.

Pregunta de seguimiento 5: ¿Qué pasa si diferentes cambios de letras tienen costos distintos?

El grafo se vuelve ponderado, por lo que las capas de BFS ya no representan el costo mínimo. Usa Dijkstra para costos no negativos, generando los mismos vecinos implícitos pero ordenando la frontera por costo acumulado. Una heurística admisible válida puede permitir el uso de A*, pero la distancia de Hamming es admisible únicamente tras escalarla por un límite inferior demostrado sobre el costo de cualquier cambio de carácter restante.

Pregunta de seguimiento 6: ¿Qué pasa si el alfabeto es Unicode o las palabras tienen longitudes diferentes?

Define primero las operaciones válidas. Los puntos de código Unicode y los grupos de grafemas son unidades distintas, y las operaciones de inserción o eliminación introducen aristas que cambian la longitud. La generación por sustitución directa ya no cubre el grafo. Según el contrato, utiliza una búsqueda indexada de vecinos a distancia de edición uno, un trie o contenedores por longitud y patrón, e incluye reglas de normalización en la igualdad y el cálculo de hash.

Pregunta de seguimiento 7: ¿Cómo demostrarías la condición de parada bidireccional en una entrevista?

Asigna a cada frontera actual una profundidad desde su propio extremo. El algoritmo avanza exactamente una capa completa de profundidad por iteración. Antes de una expansión, sequence_length es la suma de las dos profundidades de frontera más uno. Por lo tanto, una arista generada hacia la frontera opuesta forma un camino con sequence_length + 1 palabras. Si existiera un camino más corto, contendría una arista entre dos capas con una suma de profundidades menor, y esas capas ya habrían sido expandidas y conectadas. Eso contradice que este sea el primer encuentro entre fronteras.

Pregunta de seguimiento 8: ¿Cómo validarías la búsqueda optimizada más allá de ejemplos puntuales?

Para diccionarios aleatorios pequeños, conecta explícitamente cada par cuya distancia de Hamming sea uno y ejecuta un oráculo con BFS simple. Compara la respuesta con el BFS bidireccional a lo largo de miles de casos generados. Añade invariantes que aseguren que ninguna frontera interseque con unvisited, que ninguna palabra se descubra dos veces y que cada palabra de la siguiente frontera difiera en un carácter de una palabra de la frontera actual. Esto separa la evidencia de corrección de unas pocas salidas seleccionadas manualmente.