py_word_ladder · Python

▶ Aprender py_word_ladder (Python) paso a paso · explicación de py_word_ladder

Código línea a línea

Tres columnas: el código, el trozo del subject o del main que obliga a escribir esa línea, y el por qué.

py_word_ladder.py

Código	Subject	Por qué
`def word_ladder(start: str, end: str, sentence: list[str]) -> int:`	`def word_ladder(start: str, end: str, sentence: list[str]) -> int:`	Firma del subject. Devuelve un `int`.
`words = set(sentence)`	All intermediate words must exist in `sentence`.	Diccionario como `set`: comprobar si una palabra existe pasa a ser O(1).
`if end not in words:`	Return 0 if no transformation sequence is possible.	Si el destino no está en el diccionario, no hay escalera posible. Corto ya.
`return 0`	Return 0 if no transformation sequence is possible.	Cero.
`frontier = [start]`	shortest transformation sequence from a `start` word	BFS por niveles: `frontier` son las palabras a distancia `steps`.
`seen = {start}`		Palabras ya alcanzadas: no vuelvo a ellas (si no, bucles infinitos).
`steps = 1`	including `start` and `end`	Cuento palabras, no saltos: `start` sola ya es 1.
`while frontier:`		Mientras haya palabras en el nivel actual.
`next_frontier = []`		Aquí van las del nivel siguiente.
`for word in frontier:`		Cada palabra del nivel.
`if word == end:`	Return the total number of words in the shortest ladder	Llegué: BFS garantiza que es el camino más corto.
`return steps`		Devuelvo el número de palabras.
`for candidate in neighbours(word, words):`	Each transformation step must change exactly one single character.	Palabras del diccionario a una letra de distancia.
`if candidate not in seen:`		Solo las nuevas.
`seen.add(candidate)`		Marco al meter, no al sacar: así no entra dos veces en el mismo nivel.
`next_frontier.append(candidate)`		Al nivel siguiente.
`frontier = next_frontier`		Avanzo un nivel.
`steps += 1`		Una palabra más en la escalera.
`return 0`	Return 0 if no transformation sequence is possible.	Cero.


`def neighbours(word, words):`	Each transformation step must change exactly one single character.	Generador de vecinos: cambio cada posición por cada letra y me quedo con las que existen.
`for i in range(len(word)):`		Cada posición.
`for letter in "abcdefghijklmnopqrstuvwxyz":`		Cada letra. 26 × largo intentos por palabra, mucho mejor que comparar contra todo el diccionario cuando es grande.
`candidate = word[:i] + letter + word[i + 1:]`		La palabra con esa letra cambiada.
`if candidate != word and candidate in words:`	exactly one single character	Distinta a la original (exactamente un cambio) y presente en el diccionario.
`yield candidate`		La devuelvo.