McCreavy

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
*/
// 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.

1