Word Ladder

Try to solve the Word Ladder problem.

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 can 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 the 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 the words

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

Examples#

Created with Fabric.js 3.6.6 Sample example 1 src dog words hog dot pot pop mop map cap cat dest cat Input 1 Input 2 Input 3 Output 8 Output dog dot pot pop mop map cap cat Shortest tranformation sequence ---------------------------------------------------------------------------------------- Starting from "dog", we could use the dictionary words to create atransformation that ends up at "cat".

1 of 3

Created with Fabric.js 3.6.6 src dog dest cat Input 1 Input 2 Input 3 Output Sample example 2 words hog dot pot pop mop map cap can Output 0 ---------------------------------------------------------------------------------------- Shortest transformation sequence Since "cat" is not in words, there is no valid transformation sequence.

2 of 3

Created with Fabric.js 3.6.6 Input 1 Input 2 Input 3 Output Output 0 src wire dest beer words ware bare baar beer seer seen meen meet Sample example 3 ---------------------------------------------------------------------------------------- Shortest transformation sequence There is no valid transformation sequence from "wire" to "beer".

3 of 3

Understand the problem#

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

Word Ladder

1

What’s the correct output for the following inputs?

src = “hit”

dest = “cog”

words = [“log”, “dot”, “lot”, “dog”, “hot”, “cog”]

A)

5

B)

6

C)

0

D)

7

Question 1 of 30 attempted

Figure it out!#

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Drag and drop the cards to rearrange them in the correct sequence.

Create a set from the given words, a queue, and a counter to store the length of the sequence.

Push the src word into the queue.

Pop a word from the queue and find all the words in the set that differ by one character from the popped word. Push all such words in the queue and remove them from the set.

Repeat the above step until the queue is empty or the dest word has not been found. Additionally, increment the counter in every iteration.

Return the value of the counter once the the dest word has been found.

Try it yourself#

Implement your solution in the following coding playground.

Python
usercode > main.py
Input #1
Input #2
Input #3
%0 node_01 hot node_11 dot node_21 lot node_31 log node_41 cog
Visualization for Input #3
Word Ladder

Solution: Rotting Oranges

Solution: Word Ladder