AlgoViz
HomeGraphs

Word Ladder

Medium

Shortest path in a word graph

Problem

Return the shortest transformation length from beginWord to endWord changing one letter at a time.

In simple words

BFS over words that differ by one letter; the first time you reach the end is the shortest ladder.

The idea

BFS level by level from the start word, replacing one letter at a time and keeping only transformations present in the dictionary. The level at which the end word appears is the shortest length.

The trick

  • Erase visited words from the set to avoid revisiting.
  • Return 0 when the end word is not in the dictionary.
R
F
F
F
F
·
·
F
F
minute0
fresh6

Step 1 of 6. Every rotten orange (R) rots its fresh (F) neighbours each minute — a multi-source BFS. minute 0, fresh 6.

1/6
Optimal
timeO(rows·cols)spaceO(rows·cols)

All sources start at minute 0.

1// enqueue all rotten cells; BFS by layers,2// converting fresh neighbors, counting minutes.3while (q.length && fresh > 0) {4  minutes++;5  for (let n = q.length; n > 0; n--) spread(q.shift());6}7return fresh === 0 ? minutes : -1;

Input

grid
3 × 3

Memory

minute
0
fresh
6

Output

minute
0
fresh
6
answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
begin = "hit", end = "cog", words = ["hot","dot","dog","lot","log","cog"]
Output:
5
Explanation:
hit→hot→dot→dog→cog is 5 words long.

Example 2

Input:
begin = "a", end = "c", words = ["a","b","c"]
Output:
2
Explanation:
a→c directly → length 2.

Example 3

Input:
begin = "hit", end = "cog", words = ["hot","dot","dog","lot","log"]
Output:
0
Explanation:
'cog' missing → 0.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.