word-ladder-length.js

// https://oj.leetcode.com/problems/word-ladder/
function replaceChar(str, index, character) {
  return str.substr(0, index) + character + str.substr(index + 1);
}

function ladderLength(start, end, dict) {
  var dictTable = {};
  var endTable = {};

  for (var j = 0; j < end.length; j++) {
    endTable[replaceChar(end, j, '?')] = i;
  }

  for (var i = 0; i < dict.length; i++) {
    for (var j = 0; j < dict[i].length; j++) {
      dictTable[replaceChar(dict[i], j, '?')] = i;
    }
  }

  function solve(str, solutions) {
    var min = Infinity;
    var minSolution = null;

    for (var j = 0; j < str.length; j++) {
      var strKey = replaceChar(str, j, '?');

      if (strKey in endTable) {
        
        solutions.push(end);
        return solutions;
        
      } else if (strKey in dictTable && solutions.indexOf(dict[dictTable[strKey]]) === -1) {
        
        var solutionsCopy = solutions.slice();
        solutionsCopy.push(dict[dictTable[strKey]]);
        var parts = solve(dict[dictTable[strKey]], solutionsCopy);
        
        if (parts !== null && parts.length < min) {
          min = parts.length;
          minSolution = parts;
        }
        
      }
    }
    return minSolution;
  }
  var parts = solve(start, [start]);
  return parts;
}

ladderLength("hit", "cog", ["hot","dot","dog","lot","log"])