Random question time, taken from LeetCode:

Given two words (start and end) along with a dictionary, find all shortest transformation sequences from start to end such that: - Only one letter can be changed at a time - Each intermediate word must exist in the dictionary

The given example is:

start = "hit" end = "cog" dict = ["hot", "dot", "dog", "lot", "log"]

with the solution being:

[ ["hit","hot","dot","dog","cog"], ["hit","hot","lot","log","cog"] ]

First thought is: do we need to be exhaustive? There's probably some tweak where, if our path is longer than a solution we've already found, we can quit searching... But let's just get a solution that searches all the possibilities before doing any optimizing.

This looks recursive-y, but I don't think we have to carry any knowledge forward -- we can "build a larger solution on the way out."

I know if our end is "cog" and we can get from "dog -> cog", we could extend that solution to "dot -> dog -> cog" as we pop out of a recursive search.

First stab:

/**
 * @param {!string} start
 * @param {!string} end
 * @param {!Array} dict
 * @return list of solutions connecting @start to @end using @dict
 */
function wordLadder(start, end, dict) {
  // exit case - end is a neighbor of start.
  if (neighbor(start, end)) {
    return [ [ start, end ] ];
  }

  // reduce case: solve for all neighbors of start.
  var result = [];
  var neighborList = neighbors(start, dict);
  for (var i = 0 ; i < neighborList.length ; i++) {
    var neighbor = neighborList[i];

    // Make a copy of the dictionary with the neighbor removed.
    var reducedDict = dict.slice(0);
    reducedDict.splice(reducedDict.indexOf(neighbor), 1);

    // Solve the reduced problem. 
    var partialResult = wordLadder(neighbor, end, reducedDict);

    // Prefix the start onto all these results.
    for (var j = 0 ; j < partialResult.length ; j++) {
      partialResult[j].unshift(start);
      result.push(partialResult);
    }
  }
  return result;
}

/**
 * @param {!string} a
 * @param {!string} b
 * @return true if a and b differ by a single character.
 */
function neighbor(a, b) {
  var diffCount = 0;
  if (a.length != b.length) {
    return false;
  }
  for (var i = 0 ; i < a.length ; i++) {
    if (a[i] != b[i]) {
      if (++diffCount > 1) {
        return false;
      }
    }
  }
  return 1 == diffCount;
}

/**
 * @param {!string} a
 * @param {!Array} dict
 * @return list of neighbors of @a present in @dict.
 */
function neighbors(word, dict) {
  var neighbors = [];
  for (var i = 0 ; i < dict.length ; i++) {
    if (neighbor(word, dict[i])) {
      neighbors.push(dict[i]);
    }
  }
  return neighbors;
}

Does this work? Maybe.

Achievement unlocked.

Year: 2015, Location: Mountain View, Peach: Pitted