AlgoDaily - Climbing the Word Ladder

Climbing the Word Ladder (Hard)

Good morning! Here's our prompt for today.

You may see this problem at Databricks, Twilio, Gitlab, Thoughtspot, Sumo Logic, Pipedrive, Zoom, and Sonos.

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:

SNIPPET

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

Two possible sequences of transformations are given below:

SNIPPET

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:

All words in the dictionary are of the same length.
The end word is present in the dictionary. If it is not present, 0 is returned.
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)

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);
}

OUTPUT

Results will appear here.