AlgoDaily - Climbing the Word Ladder

Good morning! 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:

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)

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?

We can look at this problem as a search problem of an undirected graph, where each node represents a word. We'll denote the start state by startW and goal state by endW. Two adjacent nodes are those that can be transformed into one another and have a difference of only one character.

To find the shortest sequence of words from the start to the goal state, we'll do a breadth first search. To implement breadth first search, a queue data structure is required. The figure below shows how search proceeds. The start state is four and goal state is hoop. The search is initialized by pushing the word four into the queue.

The search algorithm pops each word from the queue in a first in first out manner. In our example, the four is popped and its adjacent words are searched in the dictionary. Three such words are found, i.e., foum, hour and cour, which are again pushed into the queue one by one. This process is repeated till either the goal state is found or the entire dictionary has been searched.

Note that a search tree is implicitly being built, i.e., it is not physically present in memory, but its implicit representation is there. The queue is the data structure that keeps track of all nodes that need to be explored in a breadth first manner. This queue is also shown in the figure as Q.

The Pseudo-Code

The pseudo-code here is a representation of the search procedure.

Time Complexity

To find whether or not two words are adjacent, n comparisons are required, where n is the length of each word. In the worst-case scenario, all pairs of words would be compared by making (O(m^2)) comparisons. If there are m words, the time complexity is (O(m^2n)). We are using the queue data structure, which in the worst-case scenario would have m entries, making the space complexity O(mn).

Concluding Remarks

We have described a simple algorithm based on breadth first search to solve the word ladder. The algorithm can be made more efficient by pre-processing and using a more complex data structure to store an intermediate representation of words that would make searching through the dictionary more efficient and faster. However, this would be at the cost of increasing the space complexity.

xxxxxxxxxx
 
Method: solve
Input: startW, endW, dictionary
​
Data structure: Queue Q of nodes.
               Node data is called strNode that keeps track of the word and level
​
1. level = 1
2. Add to the end of queue (startW,level). 
3. Remove from dictionary (startW)
4. Repeat till endW found or dictionary is empty
    i.   Remove word w and level from front of queue
    ii.  Search dictionary for all words adjacent to w 
    iii. If an adjacent word is endW then stop
    iv.  level = level+1
    iv.  Add to the end of queue all adjancent (word,level) pairs
    v.   Remove all adjacent words from dictionary
5. Return level

One Pager Cheat Sheet

The problem is to find the shortest sequence of words with a one letter difference between successive words, which transforms a given startW to a given endW using words from a provided dictionary, with time complexity of O((m^2)*n) and space complexity of O(m*n).
We can solve the problem of finding the shortest sequence of words between a start state startW and a goal state endW by using a queue data structure to do a breadth first search on an undirected graph.
The word ladder can be solved with a simple breadth-first search algorithm with a time complexity of (O(m^2n)) and space complexity of O(mn).

This is our final solution.

To visualize the solution and step through the below code, click Visualize the Solution on the right-side menu or the VISUALIZE button in Interactive Mode.

xxxxxxxxxx
 
var assert = require('assert');
​
function wordLadder(begin, end, wordList) {
  let len = 1;
  let queue = [begin];
  const dict = new Set(wordList);
  const seen = new Set(queue);
​
  while (queue.length) {
    const next = [];
    for (let node of queue) {
      if (node === end) {
        return len;
      }
​
      const splitNode = node.split('');
      for (let i = 0; i < splitNode.length; i++) {
        for (let d = 0; d < 26; d++) {
          splitNode[i] = String.fromCharCode(97 + d);
          const nv = splitNode.join('');
          if (!seen.has(nv) && dict.has(nv)) {
            next.push(nv);
            seen.add(nv);
          }
          splitNode[i] = node[i];
        }
      }
    }
    queue = next;
    len++;
  }
​
  return 0;
}
​
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);
}

Got more time? Let's keep going.

If you had any problems with this tutorial, check out the main forum thread here.