我编写了以下算法来完成单词阶梯。您可以在我的github上找到完整的程序,包括jQuery可视化和json字典:https://github.com/NateBrady23/algorithms/tree/master/word_ladder
所以除了我用一些节点的每个级别来填充一些数组之外,我对我使用的算法名称和正在构建的数据结构名称几乎没有什么了解。
我从给定的输入单词和结束单词开始。我消除了字典中我不能使用的所有单词(输入单词和长度与输入单词不同的单词)。我构建了一个Node对象,它保存了跳转级别、值和prev,这样我如果找到路径,就可以从我的终点向后遍历。
从0级开始,我找到可以通过转换一个字母来创建的所有单词,并将其保存在1级wordNodes桶中。每个节点对象的prev属性指向它所在的0级节点。然后我从字典中删除所有这些单词。接下来,我遍历所有的1级wordNodes,对于每个节点,从修改过的字典中找到转换后的单词并存储在2级中,并指向创建它的单词,以此类推,直到找到目标单词或无法创建新级别(无法到达我的单词)。
鉴于上述可能表述不佳的摘要,我构建了这种类型的结构(如二叉搜索树)和我使用的算法是否有名称?此外,是否有一种方法可以显著改进下面的代码而不使用完全不同的结构/算法。
我从给定的输入单词和结束单词开始。我消除了字典中我不能使用的所有单词(输入单词和长度与输入单词不同的单词)。我构建了一个Node对象,它保存了跳转级别、值和prev,这样我如果找到路径,就可以从我的终点向后遍历。
从0级开始,我找到可以通过转换一个字母来创建的所有单词,并将其保存在1级wordNodes桶中。每个节点对象的prev属性指向它所在的0级节点。然后我从字典中删除所有这些单词。接下来,我遍历所有的1级wordNodes,对于每个节点,从修改过的字典中找到转换后的单词并存储在2级中,并指向创建它的单词,以此类推,直到找到目标单词或无法创建新级别(无法到达我的单词)。
鉴于上述可能表述不佳的摘要,我构建了这种类型的结构(如二叉搜索树)和我使用的算法是否有名称?此外,是否有一种方法可以显著改进下面的代码而不使用完全不同的结构/算法。
<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>