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++;

  }

​

That's all we've got! Let's move on to the next tutorial.

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