https://stackoverflow.com/questions/32529282

by juvian

JavaScript

var start = "hit"
var end = "cog"
var words = [start,end,"hot","dot","dog","lot","log", "asdasd", "sssss", "fog", "sog", "koj"]



var dict = {}

for(var i=0;i<words.length;i++){
	if(words[i].length == start.length){ // filter out different lengths 
    	dict[words[i]] = null;
    }
}

var queue1 = [start];
var queue2 = [end];

var found = false;

function addNeighbours(word, queue, type){ // word we come from, queue we need to add the words to (queue1 if we travel from start, queue2 from end and type 1 or 2)
	for(var i =0;i<word.length;i++){ // for each character on word
        for(var j=97;j<=113;j++){ // create all posible words with letter change on ith position
        	var newWord = word.substring(0,i)+String.fromCharCode(j)+word.substring(i+1,word.length);
            if(String.fromCharCode(j) != j){ // if its not the word we came from
            	checkWord(newWord)
            }
        }
    }
    
    function checkWord(newWord){
		if(dict.hasOwnProperty(newWord)){ // if word exists in dict
            if(dict[newWord] == null){ // if we hadn't found it before
                dict[newWord] = {from:word, type: type}; // we mark it as found
                queue.push(newWord); // we add the word to the queue
            }else{
                if(dict[newWord].type != type){ // if we found it on a diferent direction, it means we found it on both directions, so this is the shortest path
                    found = dict[newWord];
                    dict[newWord].found = word;
                    dict[newWord].word = newWord
                    return 0;
                }
            }
        }    
    }
    
}

function findPath(){
	if(queue1.length && !found){
    	addNeighbours(queue1.shift(), queue1, 1)
    }
    if(queue2.length && !found){
    	addNeighbours(queue2.shift(), queue2, 2)
    }
    if(!found){
    	if(queue1.length || queue2.length){
        	findPath();
        }
    }
}
findPath()

if(!found){
	console.log("not found")
}else{ // build...