Good evening! Here's our prompt for today.

Imagine two words placed at the two ends of a ladder. Can you reach one word from another using intermediate words as rings of the ladder? Each successive or transition word has a difference of only one letter from its predecessor, and must belong to a provided dictionary. Can we achieve this using the shortest possible number of rings, and return that number?

The Problem

Suppose we are given:

• a dictionary of words
• a start word
• an end word

We have to find a minimum length sequence of words so that the start word is transformed into the end word. A word is only transformable to the other if they have a difference of one letter. Consider a dictionary, start word startW, and end word endW below:

1Dictionary: {hope, hole, bold, hold, cold, sold, dold}
2startW: bold
3endW: hope

Two possible sequences of transformations are given below:

1Sequence 1: bold->cold->sold->hold->hole->hope
2Sequence 2: bold->hold->hole->hope

The length of the second sequence is 4, which is shorter than sequence 1 with a length of 6. Hence the acceptable answer is 4. We make the following assumptions for this problem:

1. All words in the dictionary are of the same length.
2. The end word is present in the dictionary. If it is not present, 0 is returned.
3. The comparison with words in the dictionary is case sensitive. So abc is not the same as ABC.

Constraints

• The number of words in the dictionary <= 50
• The length of each word in the dictionary and start word <= 50
• The strings will only consist of lowercase and uppercase letters
• Let n be the length of each word and m be the number of words
• Expected time complexity :O((m^2)*n)
• Expected space complexity : O(m*n)

Try to solve this here or in Interactive Mode.

How do I practice this challenge?

xxxxxxxxxx

var assert = require('assert');

​

function wordLadder(begin, end, wordList) {

  // fill this in

}

​

try {

  assert.equal(

    wordLadder('bold', 'hope', [

      'hope',

      'hole',

      'bold',

      'hold',

      'cold',

      'sold',

      'dold',

    ]),

    4

  );

​

  console.log(

    'PASSED: ' +

      "`wordLadder('bold', 'hope', ['hope', 'hole', 'bold', 'hold', 'cold', 'sold', 'dold'])` should return `4`"

  );

} catch (err) {

  console.log(err);

}

​

Here's our guided, illustrated walk-through.

How do I use this guide?