DevOps NetworkDevOpsNetwork
Join Free
Advanced

Word Ladder

hardAdvanced graphs Must-do

Problem statement

You have a start word beginWord, a target word endWord, and a list of allowed words wordList. All words have the same length and use lowercase letters.

In one move you change exactly one letter of the current word, and the result must be a word in wordList (beginWord itself does not need to be in the list). Find the shortest chain of moves from beginWord to endWord and return how many words that chain contains, counting both ends. If endWord cannot be reached, return 0.

Examples

Example 1

Input: beginWord = "cold", endWord = "warm", wordList = ["cord","card","ward","warm","worm","word","wore"]

Output: 5

Explanation: One shortest chain is cold → cord → card → ward → warm. That is 5 words (4 moves). cold → cord → word → worm → warm ties it.

Example 2

Input: beginWord = "ping", endWord = "pong", wordList = ["pint","pant"]

Output: 0

Explanation: pong is not in the list, so no chain can end there.

Hints

Approach

Same BFS, but generate neighbours instead of scanning for them. For the current word, try every position and every letter a to z. If the new string is in the set of unvisited words, it is a neighbour: remove it from the set (that marks it visited) and enqueue it.

That costs 26 · L candidate strings per word, each taking O(L) to build and hash, independent of how long the list is. Processing the queue level by level keeps the word count in a single variable.

ComplexityTime O(N · L² · 26)Space O(N · L)
Python
from collections import deque
from string import ascii_lowercase
def ladder_length(begin_word, end_word, word_list):
unvisited = set(word_list)
if end_word not in unvisited:
return 0
unvisited.discard(begin_word)
queue = deque([begin_word])
steps = 1
while queue:
for _ in range(len(queue)):
word = queue.popleft()
if word == end_word:
return steps
for i in range(len(word)):
for ch in ascii_lowercase:
cand = word[:i] + ch + word[i + 1:]
if cand in unvisited:
unvisited.remove(cand)
queue.append(cand)
steps += 1
return 0
print(ladder_length("cold", "warm", ["cord", "card", "ward", "warm", "worm", "word", "wore"]))
print(ladder_length("ping", "pong", ["pint", "pant"]))

Follow-up questions

  • Run BFS from both ends at once and always expand the smaller frontier. Why does that cut the work so much?
  • Return every shortest chain, not just its length (Word Ladder II: BFS to build parent links, then DFS to list the paths).

Frequently asked questions

It checks whether you can spot a graph that is never handed to you as a graph. The nodes and edges are implicit and you have to generate them on demand, which is the same skill as exploring states in a deployment or rollout system without materialising every state first. It also tests BFS and the cost of neighbour generation, both common in the harder SWE-style infra loops.

Removing on enqueue guarantees each word enters the queue once. If you only marked words when dequeued, the same word could be added many times from different parents at the same level, which wastes time and memory on large lists.

When the list is tiny and the words are long. Generating neighbours costs 26 · L lookups per word no matter how short the list is. For typical inputs, lists are much longer than 26 times the word length, so generation is faster.