For a big dictionary, the following code gives a time limit error. I was trying to use ES6 constructs in the code. The inputs that gave TLE are here.

I have tried to use BFS for the problem, adding words in the Q only if it has not been visited and it exists in the dictionary.

function getShortestPathBetweenWords(st, end, dict) {
if (st === end) {
return 1;
}
if (st.length < end.length) {
return 0;
}
let q = [];
let isVisited = new Map();
q.push(st);
let level = 0;
while (q.length!== 0) {

level++;
let size = q.length;
for (let i = 0; i < size; i++) {
let newWord = q.shift();
if (newWord === end) {
return level;
}
let listOfWords = _generateNewWords(newWord, dict);

for (let i = 0; i < listOfWords.length; i++) {
if (isVisited.get(listOfWords[i]) !== true) {
q.push(listOfWords[i]);
isVisited.set(listOfWords[i], true);
}
}

}

}
return 0;
}
/**
* to generate new words from given Words
*/
function _generateNewWords(word, dict) {
let len = word.length;
let listOfWords = [];
let alphabhets = 'abcdefghijklmnopqrstuvwxyz'.split('');
for (let i = 0; i < len; i++) {
for (let j = 0; j < 26; j++) {
let charArray = word.split('');
charArray[i] = alphabhets[j];
if (checkinDictionary(charArray.join(""), dict) === true) {
listOfWords.push(charArray.join(""));
}
}
}
return listOfWords;
}
/**
* checkinDictionary
*/
function checkinDictionary(str, dict) {
for (let i = 0; i < dict.length; i++) {
if (dict[i] == str) {

return true;
}
}
return false;
}

• It would be nice to add a specific testcase your code fails about. Or does it at least for all of them? Apr 23 '17 at 20:39
• I actually added the specific inputs it fails for in the gist .Apologies if it was not clear enough Apr 23 '17 at 20:42

Naming

I suggest renaming getShortestPathBetweenWords() to findShortestLadderDistance() for the following reasons:

• get is recommended as a prefix for simple lookup functions. Use another verb such as compute or find for meatier, computationally heavier functions.
• You are actually computing the distance of the shortest path, not the path itself. And a ladder is a more specific word for path whose neighboring words differ by exactly one substitution.

Further naming suggestions:

• Rename _generateNewWords() to generateNeighbors()
• Rename level to distance
• Rename st to start
• Rename newWord to next
• Rename q to queue
• Rename listOfWords to neighbors
• Rename charArray to chars

Style

Instead of while (queue.length !== 0) I suggest the more self-documenting while (queue.length > 0) as the length can never be negative.

Also, don't needlessly mix "" vs. '' for strings.

Specification

Right now you are returning a distance of 0 when there is no path and a distance of 1 if start equals end. I suggest following the common definition of path length and return Infinity and 0 instead.

You might also want to pass the alphabet as a parameter instead of having a hard-coded 'magic' constant in your _generateNewWords() function. It can easily be computed from your dictionary as alphabet = [...new Set(dict.join(""))].

Also, you currently allow any word for start while end must be part of the dictionary. I recommend allowing non-dictionary words in both cases for consistency.

Performance

Your main performance bottleneck is the checkinDictionary() function. If you keep track of a set of open words which you haven't visited yet, you can replace that function call with a simple open.has(word). Set lookup time is constant and thus much faster than iterating the whole dict array.

You then have to pass the open set to generateNeighbors(). The isVisited map is no longer needed.

Another performance drain is performing string splitting via let charArray = word.split('') in the inner loop of _generateNewWords. You can push that to the outer loop.

Also, you currently treat start.length < end.length as a special 'shortcut' case. You could generalize this to start.length != end.length.

Sample code

Applying all those modifications to your code yields:

function findShortestLadderDistance(start, end, alphabet, dict) {
if (start === end) return 0;
if (start.length != end.length) return Infinity;

let queue = [start];
let distance = 1;
let open = new Set(dict);
open.delete(start);

while (queue.length > 0) {
for (let i = 0, length = queue.length; i < length; i++) {
let next = queue.shift();

for (let neighbor of generateNeighbors(next, alphabet, open)) {
if (neighbor === end) return distance;

queue.push(neighbor);
open.delete(neighbor);
}
}
distance++;
}
return Infinity;
}

function* generateNeighbors(word, alphabet, open) {
let chars = word.split("");

for (let i = 0; i < chars.length; i++) {
let char = chars[i];

for (let j = 0; j < alphabet.length; j++) {
chars[i] = alphabet[j];
neighbor = chars.join("");
if (open.has(neighbor)) yield neighbor;
}
chars[i] = char;
}
}

let start = "sand";
let end = "acne";
console.log(findShortestLadderDistance(start, end, alphabet, dict));