Word Ladder

Problem

Given begin and end words of equal length and a dictionary words, return the number of words in the shortest transformation sequence from begin to end, changing one letter at a time so every intermediate word is in the dictionary.

Run BFS over the word set, expanding only candidates at Hamming distance 1. Return 1 when begin equals end and 0 when end is not in the dictionary.

Hint

The sequence length counts both endpoints; each BFS layer is one more letter change.

Test cases

case 1

in: ["hit","cog",["hot","dot","dog","lot","log","cog"]]

expected: 5

case 2

in: ["hit","cog",["hot","dot","dog","lot","log"]]

expected: 0

case 3

in: ["a","c",["a","b","c"]]

expected: 2

case 4

in: ["hot","hot",["hot"]]

expected: 1

case 5

in: ["a","b",[]]

expected: 0

Starter codePython

def ladder_length(begin, end, words):
    # Your code here
    pass

5 test cases · run your code against them in the editor