Word ladder, shortest transformation with BFS
Asked at Jane Street
You are given a begin word, an end word, and a dictionary of allowed words. Each step changes exactly one letter, and every intermediate word must be in the dictionary.
begin = "hit", end = "cog"
words = ["hot", "dot", "dog", "lot", "log", "cog"]
-> 5 # hit -> hot -> dot -> dog -> cog (5 words in the chain)
Return the number of words in the shortest transformation chain including both ends, or 0 if none exists.
Your answer
This one is open-ended. Work it through, then check your reasoning against the full solution.