Solution: Word Ladder

Let's solve the Word Ladder problem using the Tree Breadth-first Search pattern.

We'll cover the following

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 00.

A transformation sequence is a sequence of words ((src →\to word1word_1 →\to word2word_2 →\to word3word_3 ...... →\to wordjword_j)) that has the following properties:

  • wordj=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≤1 \leq src.length ≤10\leq 10

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

  • src ≠\neq dest

  • 1≤1 \leq words.length ≤5000\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 11 while returning the length to count dest in the length of the shortest transformation sequence.

Let’s look at an example below:

Created with Fabric.js 3.6.6 src hit dest cog queue level 0 words dot hot dog lot log cog set dot hot dog lot log cog Create a set using the available words for fasterlookup, a queue for the BFS aprroach, and a length variable to store the length of the sequence.

1 of 12

Created with Fabric.js 3.6.6 dest cog src hit queue hit level 1 set dot hot dog lot log cog words dot hot dog lot log cog Push the src word ("hit") into the queue and increment the length.

2 of 12

Created with Fabric.js 3.6.6 dest cog src hit queue hit level 1 words dot hot dog lot log cog set dot hot dog lot log cog Pop a word ("hit") from the queue, and check all words inthe set that differ by one character from the popped word.

3 of 12

Created with Fabric.js 3.6.6 dest cog src hit queue hot level 2 words dot hot dog lot log cog set dot hot dog lot log cog Push all the words ("hot") into the queue that differ byone character from the popped word ("hit"), removethem from the set, and increment the length.

4 of 12

Created with Fabric.js 3.6.6 dest cog src hit queue hot level 2 words dot hot dog lot log cog set dot dog lot log cog Pop a word ("hot") from the queue, and check all the wordsthat differ by one character from the popped word.

5 of 12

Created with Fabric.js 3.6.6 dest cog src hit queue dot lot level 3 words dot hot dog lot log cog set dot dog lot log cog Push all the words ("dot" and "lot") into the queue that differby one character from the popped word "hot", remove them from the set, and increment the length.

6 of 12

Created with Fabric.js 3.6.6 dest cog src hit queue dot lot level 3 words dot hot dog lot log cog set dog log cog Pop a word ("dot") from the queue, and check all the wordsthat differ by one character from the popped word.

7 of 12

Created with Fabric.js 3.6.6 dest cog src hit queue lot dog level 3 words dot hot dog lot log cog set dog log cog Push all the words ("dog") into the queue that differ byone character from the popped word "dot", and removethem from the set.

8 of 12

Created with Fabric.js 3.6.6 dest cog src hit queue lot dog set log cog level 3 words dot hot dog lot log cog Pop a word ("lot") from the queue, and check all the wordsthat differ by one character from the popped word.

9 of 12

Created with Fabric.js 3.6.6 dest cog src hit set log cog queue dog log level 4 words dot hot dog lot log cog Push all the words ("log") into the queue that differ byone character from the popped word "lot", removethem from the set, and increment the length.

10 of 12

Created with Fabric.js 3.6.6 dest cog src hit set cog queue dog log level 4 words dot hot dog lot log cog Pop a word ("dog") from the queue, and check all the wordsthat differ by one character from the popped word.

11 of 12

Created with Fabric.js 3.6.6 dest cog src hit set cog queue log level 5 words dot hot dog lot log cog Since the word "cog" is the dest word, we return length + 1as the length of the shortest transformation sequence.

12 of 12

Let’s implement the algorithm as discussed above:

Word Ladder

Time complexity#

The time complexity of this solution is O(N2×M)O(N^2 \times M), where NN represents the number of words, and MM represents the length of each word.

Space complexity#

The space complexity of this solution is O(N)O(N), where NN represents the number of words.

Word Ladder

Final Remarks