Your free access ends in 7 days — and you haven’t tried it yet. Watch one algorithm run, start to finish. It takes about two minutes.

Try one problem
0
Problem

Word Ladder

LeetCode #127Hard
Shortest transformation sequence via BFS

Given beginWord, endWord and a word list, return the length of the shortest transformation sequence from beginWord to endWord, changing one letter at a time, where every intermediate word is in the list (or 0 if impossible).

Asked atAmazonGoogleMeta
step 1 / 27
word graph (one-letter edges)
hit
hot
dot
lot
dog
log
cog
BFS queue
front →
(empty)
← back
Words as a graph + BFS for the shortest ladder
▸
1build graph: edge(a, b) if a, b differ by one letter
2queue = [beginWord]; dist[beginWord] = 1; visited = {beginWord}
3while queue: u = queue.pop_front()           // dequeue (level order)
4    for v in neighbours(u):
5        if v in visited: continue            // already shortest
6        dist[v] = dist[u] + 1; enqueue v      // first time = shortest
7    if u == endWord: return dist[u]           // BFS ⇒ shortest ladder
8return 0                                       // unreachable
state
  • beginhit
  • endcog
  • goalfewest words

line 1Word Ladder (LeetCode 127): transform "hit" into "cog", changing ONE letter at a time, and every intermediate word must be in the word list. Model it as a GRAPH — each word is a node, and an edge joins two words that differ by exactly one letter. The answer is the SHORTEST ladder length (count of words on the path). Shortest path on an unweighted graph = BFS.