Introduction

Word Ladder is one of the most famous BFS shortest path problems.

You are given:

  • beginWord
  • endWord
  • wordList

Goal:

Find the length of the shortest transformation sequence from beginWord to endWord.

Rules:

  • Change only one character at a time.
  • Every transformed word must exist in wordList.

Example

Input

beginWord = "hit"endWord = "cog"

wordList = ["hot","dot","dog","lot","log","cog"]

Output

5

Explanation

hit↓
hot
↓
dot
↓
dog
↓
cog

Length = 5

Key Observation

Each word can be treated as a graph node.

Two words are connected if they differ by exactly one character.

Since every transformation has equal cost, BFS gives the shortest path.

Algorithm

  1. Store words in a set.
  2. Push beginWord into queue.
  3. Start BFS traversal.
  4. Generate all possible one-letter transformations.
  5. If transformation exists in set, push into queue.
  6. Continue until endWord is found.
  7. Return shortest length.

Dry Run

Initial Queue

[hit]
Level 1
hit → hot

Level 2

hot → dot, lot

Level 3

dot → dog
lot → log

Level 4

dog → cog

Answer

 5

Approach : BFS

Start from beginWord and explore all valid transformations level by level.

Since BFS explores shortest paths first, the first time we reach endWord gives the answer.

Practice

Complexity Analysis

Time Complexity: O(N × L × 26)Explanation: For every word, we try changing each character position with all 26 lowercase letters. Here N is the number of words and L is the word length.

Space Complexity: O(N)
Explanation:The queue and word set store at most N words during BFS traversal.

Why This Problem is Important

Word Ladder is one of the most popular BFS shortest path interview questions and teaches graph modeling using strings.

Common Beginner Mistakes

  • Using DFS instead of BFS.
  • Not removing visited words.
  • Forgetting endWord existence check.
  • Revisiting already processed words.

Interview Tip

Always mention:

Each word represents a graph node and one-character transformations represent edges. Since all transformations have equal cost, BFS guarantees the shortest path.

Related Questions

  • Open the Lock
  • Minimum Genetic Mutation
  • Word Ladder II
  • Rotting Oranges
  • Shortest Path in Binary Matrix

Final Takeaway

Word Ladder is a classic BFS shortest path problem where words form graph nodes and valid transformations form edges. Recognizing the graph structure quickly leads to an efficient BFS solution.