Word Ladder

You are given two words:

beginWord

endWord

and a dictionary of words called wordList.

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

A transformation is valid when:

• Only one character can be changed at a time.
• Every intermediate word must exist in wordList.

If no transformation is possible, return:

-1

Example

beginWord = "hit"

endWord   = "cog"

wordList =

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

One shortest transformation is:

hit

 ↓

hot

 ↓

dot

 ↓

dog

 ↓

cog

The sequence contains 5 words.

Therefore:

5

Main Idea

This is a BFS + HashSet problem.

Treat every word as a node in a graph.

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

For example:

hit → hot

because only the third character changes:

h i t

h o t

Since every transformation costs exactly 1, BFS finds the shortest transformation.

BFS Process

Start with:

hit

Generate all possible one-character transformations:

ait

bit

cit

...

hot

...

If a generated word exists in the dictionary, add it to the queue.

Continue until:

endWord

is reached.