Word Ladder, Javascript: What algorithm and data structure am I using?

Question

I wrote the following algorithm to complete a word ladder. You can find the full program with the jQuery visualization and the json dictionary on my github here: https://github.com/NateBrady23/algorithms/tree/master/word_ladder

So I have very little knowledge of what the names of the algorithms I'm using are, and the names of the data structures I'm building out other than I'm filling some arrays with each level of Nodes.

I start at a given input word and end word. I eliminate all words in the dictionary that I can't use (the input word and words not the same length as the input word). I build a Node object that holds the jump level it's on, a value, and a prev so I can traverse backward from my endpoint if I find a path.

Starting at level 0, my input word, I find all words that could be created from that word by transforming one letter and save it into a bucket of level 1 wordNodes. Each of those Node objects prev property point back to the level 0 node it was found from. I then delete all of those words from the dictionary. I then go through all the level 1 wordNodes and for each one, find the transformed word from the modified dictionary and store it in level 2 and point back to the word that created it and so on until I find the target word or no new levels can be created (no path to my word).

So given that probably poorly worded summary, is there a name for this type of structure I've built (like a binary search tree?) and the algorithm I used to get there. Also, is there a way to significantly improve the code below without using an entirely different structure/algorithm.

<style>
    span {
        margin: 10px;
    }

    .highlight {
        background-color: yellow;
        font-weight: bold;
    }
    span {
        display: inline-block;
    }
</style>
<div id="path">

</div>

<script src='js/jquery.min.js'></script>
<script src='js/dictionary.js'></script>
<script>
// var dict = JSON.parse('{"aa" : true, "aah" : true, "aahed" : true}');

    // Build our dictionary array
    // Create a Node object so we can traverse back up the tree
    function Node(value, prev, level) {
        this.prev = prev;
        this.level = level;
        this.value = value;
    }

    function getRegex(word) {
        var temp = [];

        for(var i = 0; i < word.length; i++){
            temp.push( word.substring(0,i) + '.' + word.substring(i+1) );
        }  
        var re_str = '^(' + temp.join('|') + ')$';
        return new RegExp(re_str, 'i');
    }

    function oneOffs(wordNode) {
        var list = [];
        var regex = getRegex(wordNode.value);

        if ($('#' + (wordNode.level+1)).length == 0) {
            $('#path').append('<div id="' + (wordNode.level+1) + '"></div>');
            $('#' + (wordNode.level+1)).append('<h1>Level: ' + (wordNode.level+1));
        }
        for (var word in dict) {
                // If we found a match
                if (dict.hasOwnProperty(word) && regex.test(word)) {
                    list.push(new Node(word, wordNode, wordNode.level + 1));
                    $('#' + (wordNode.level+1)).append('<span id="' + word + '">' + word +'</span>');
                    delete dict[word];
                }
        }
        return list;
    }

    // Get our start and end words
    inputWord = 'boggle';
    endWord = 'shaggy';

    $('#path').append('<div id="start"><h1>Transform Case</h1><span><b>Starting Word:</b> ' + inputWord + '</span><span><b>Ending Word:</b> ' + endWord + '</span></div>');
    $('#path').append('<div id="0"><h1>Level: 0</h1><span id="' + inputWord + '">' + inputWord + '</span></div>');

    // Have to remove our inputWord from the dictionary
    delete dict[inputWord];

    // Remove all words in dictionary not of proper length
    for (var word in dict) {
        if (dict.hasOwnProperty(word)) {
            if (word.length != inputWord.length) {
                delete dict[word];
            }
        }
    }


    // Create input and end nodes
    inputNode = new Node(inputWord, null, 0);
    endNode = new Node(endWord, null, 0);

    // Create our initial list of level 1 nodes
    list = oneOffs(inputNode);

    for (var node in list) {
        if (list[node].value === endNode.value) {
            endNode.level = list[node].level;
            endNode.prev = list[node].prev;
        }
    }

    // Build our tree
    while (list.length && !endNode.level) {
        newList = [];
        for (var i = 0; i < list.length; i++) {
            newNodeList = oneOffs(list[i]);
            for (var node in newNodeList) {
                if (newNodeList[node].value === endNode.value) {
                    endNode.level = newNodeList[node].level;
                    endNode.prev = newNodeList[node].prev;
                    break;
                }
            }
            if (newNodeList.length) {
                newList = newList.concat(newNodeList);
            }
        }
        list = newList;
    }

    // if we found the path, let's traverse back up and print out all the values
    if (endNode.level) {
        curr = endNode;
        $('#' + curr.value).addClass('highlight');
        console.log(curr.value);
        while(curr.prev) {
            $('#' + curr.prev.value).addClass('highlight');
            console.log(curr.prev.value);
            curr = curr.prev;
        }
    } else {
        console.log('No possible path');
    }


</script>

Answer 1

The comments have noted that this is a breadth-first search, but I don't know of any specific name for this algorithm. And of course your data structure is some sort of tree.

As to optimizations, I haven't looked at the code very carefully, but one thing leaps out at me. To move from one step to another, you construct a complex regex to match each word at a particular level and then loop through the entire dictionary to see if any word in it matches this regex. It would certainly be more efficient to build the actual possible words and check whether each one is in the dictionary. That is, if you have foo, check your dictionary for aoo, boo, coo, ... zoo, fao, fbo, fco, ... fzo, foa, fob, foc, ... foz. Since you're already removing visited words from the dictionary, you won't get multiple new hits for foo in this list.

That should significantly reduce the number of checks you have to make, and it will change from a regex test to a simple property lookup. I'm guessing it would be a substantial boost to performance.