Solution: Word Ladder

Statement

Given two words, src and dest, and a list, words, return the number of words in the shortest transformation sequence from src to dest. If no such sequence could be formed, return $0$.

A transformation sequence is a sequence of words $($src $\to$ $word_1$ $\to$ $word_2$ $\to$ $word_3$ $...$ $\to$ $word_j$$)$ that has the following properties:

• $word_j =$ dest
• Every pair of consecutive words differs by a single character.
• All the words in the sequence are present in words. The src does not need to be present in words.

Constraints:

• $1 \leq$ src.length $\leq 10$

• src.length $=$ dest.length $=$ words[i].length

• src $\neq$ dest

• $1 \leq$ words.length $\leq 5000$

• No duplicates in words

• src, dest, and words[i] consist of lowercase English characters.

Solution

We will find the shortest transformation sequence using the BFS approach. We will create a set of words for faster lookup of available words, a queue to store the words that need to be checked for the transformation sequence through BFS, and a counter, length, to store the length of the sequence.

We start by pushing the src word into the queue. After that, we follow the steps given below:

1. Pop a word from the queue and store it in curr.

2. Check all the words in the set that only differ by one character from curr.

   1. Push all such words into the queue and remove them from the set.

3. Keep popping the first word from the queue into curr and finding all the adjacent words of curr that differ by only one character until we have traversed all the words or have not found the dest.

4. In each iteration, the length is incremented since each iteration checks all adjacent words (i.e., the words that differ by one character) of the popped word. Once dest is found, we return length + 1, representing the length of the sequence. We add $1$ while returning the length to count dest in the length of the shortest transformation sequence.

Let’s look at an example below: