Word ladder I
HardBFS over words differing by one letter
Problem
Return the length of the shortest transformation from beginWord to endWord, changing one letter at a time through valid dictionary words.
BFS over words that differ by one letter; the first time you reach the end is the shortest ladder.
The idea
Treat each word as a vertex with edges to every word one letter away, so the shortest transformation is an unweighted shortest path and BFS finds it. Generating neighbours by trying all 26 letters at each position beats comparing against every word in the list.
The trick
- Neighbour generation is O(length × 26), not O(dictionary size).
- Put the dictionary in a hash set and remove words as you visit them.
- The answer counts words, so start the level at 1.
Step 1 of 6. Every rotten orange (R) rots its fresh (F) neighbours each minute — a multi-source BFS. minute 0, fresh 6.
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.