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.