py_word_ladder

Código comentado línea a línea y paso a paso:

• Python · paso a paso

Entregas: py_word_ladder.py con word_ladder(start, end, sentence). Rank 05 · nivel 3.

Qué pide (en palabras normales)

• De start a end cambiando una letra por paso. Cada palabra intermedia tiene que estar en sentence.
• Devuelve cuántas palabras tiene la escalera más corta, contando start y end. hit → hot → dot → dog → cog son 5.
• Imposible → 0.

Write a function that computes the length of the shortest transformation sequence from a `start` word to an `end` word using a dictionary list of allowed words `sentence`.

Each transformation step must change exactly one single character. All intermediate words must exist in `sentence`.

The function should:
- Return the total number of words in the shortest ladder (including `start` and `end`).
- Return 0 if no transformation sequence is possible.

Expected file: py_word_ladder.py
Function signature:
def word_ladder(start: str, end: str, sentence: list[str]) -> int:

Examples:
word_ladder("hit", "cog", ["hot", "dot", "dog", "lot", "log", "cog"])
=> 5
word_ladder("hit", "cog", ["hot", "dot", "dog", "lot", "log"])
=> 0

Es un BFS

"Camino más corto" con pasos que valen todos lo mismo = búsqueda en anchura. Cada palabra es un nodo; dos palabras están conectadas si difieren en una letra. El primer nivel en el que aparece end es la respuesta.

frontier = [start]
seen = {start}
steps = 1
while frontier:
    next_frontier = []
    for word in frontier:
        if word == end:
            return steps
        for candidate in neighbours(word, words):
            if candidate not in seen:
                seen.add(candidate)
                next_frontier.append(candidate)
    frontier = next_frontier
    steps += 1
return 0

Lo hago por niveles (una lista por nivel) en vez de con deque: no necesito importar nada y el contador de pasos sale solo.

Vecinos sin recorrer todo el diccionario

def neighbours(word, words):
    for i in range(len(word)):
        for letter in "abcdefghijklmnopqrstuvwxyz":
            candidate = word[:i] + letter + word[i + 1:]
            if candidate != word and candidate in words:
                yield candidate

Para cada posición pruebo las 26 letras y miro si la palabra existe en el set. Son 26 × largo comprobaciones O(1), independiente del tamaño del diccionario. La alternativa (comparar con todas las palabras y contar diferencias) es O(n) por palabra y se come el timeout con diccionarios grandes.

Trampas

• end no está en sentence → 0 directamente, aunque esté a una letra de start.
• Cuenta palabras, no saltos: empieza en 1, no en 0.
• Marca como vista al encolar, no al desencolar. Si no, la misma palabra entra varias veces y en grafos densos explota.
• Sin from collections import deque: cualquier import suspende. La lista por niveles lo evita.
• Si start == end, devuelve 1 (el bucle lo hace solo, siempre que end esté en el diccionario).