为什么我的 BFS 算法没有返回预期的最短路径?
Why is my BFS algo not returning expected shortest path?
我正在尝试编写一个算法,该算法应该找到从给定的 beginWord 到 endWord 的最短转换路径,这样一个字母就可以一次更改。
测试用例
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log","cog"]
预期输出为 5,因为可以遵循长度为 5 的最短转换之一:
"hit" -> "hot" -> "dot" -> "dog" -> "cog"
在我的算法中,我使用队列遵循 BFS,对于每个单词,我用从 'a' 到 'z' 的所有字母替换它的每个字母,同时我检查结果单词是否存在于给定的词典中,即 wordList.
如果是,那我就把它推入队列,这样它也可以像最后一个字一样处理。否则,从队列中获取下一个条目,依此类推,直到队列为空。
现在,我的代码如下 returns hit -> hot -> dot -> lot -> dog -> log -> cog
,这是一个错误的输出。这主要是因为dot
和dog
错误地转换成了lot
。
lot
和 dog
以及一个与 dot
不同的字母,因此它们都被推入队列并稍后处理,这导致类似的问题 [= 的双重转换15=] 变成 log
和 cog
。
现在,这清楚地表明我遗漏了 BFS 和最短路径搜索的一些关键点。我如何决定我必须将 dot
转换为 dog
而不是 lot
以确保我按照最短路径到达预期目标,前提是两者都是有效的转换dot
.
这将帮助我理解和修复我的代码。
var ladderLength = function(beginWord, endWord, wordList) {
wordList = new Set(wordList);
var str = [beginWord];
var queue = [], distance = 0, i, j, len;
len = beginWord.length;
queue.push(beginWord);
while (queue.length > 0) {
var currentWord = queue.shift();
if (currentWord === endWord) {
console.log(str.join(" -> "));
return distance + 1;
}
for (i = 0; i < len; i++) {
var tempCh = currentWord[i];
for (j = 'a'; j <= 'z'; j = String.fromCharCode(j.charCodeAt(0)+1)) {
currentWord = currentWord.replaceAt(i,j);
if (wordList.has(currentWord)) {
distance++;
wordList.delete(currentWord);
str.push(currentWord);
queue.push(currentWord);
}
}
currentWord = currentWord.replaceAt(i, tempCh);
}
}
return 0;
};
String.prototype.replaceAt=function(index, replacement) {
return this.substr(0, index) + replacement+ this.substr(index + replacement.length);
}
您可以在转换字符串的同时进行一些额外的处理以获得正确的输出。在替换字母之前,将要替换的字符 (i)
与将取代它的字符 (j)
.
进行比较
为每次迭代保留一个标志变量flag
,并检查新字符j
是否会更接近EndWord
中相应位置的字符。如果它正在靠近而不是远离(例如,'d' vs 'l' for 'c' in cog),并且存在于 WordList
中,进行替换并设置 flag = true
。如果在与角色的距离相同的情况下也可以进行另一个转换,请检查标志,如果为真,则跳过它,否则进行转换。
希望对您有所帮助。
I replace each of its letter with all alphabets
表示您进行了太多有效性检查。
我建议您只用 valid 字母替换每个字母。例如"hit"中的i只能用o代替:"hot","dot","dog","lot","log","cog".
这将使程序更高效,更不容易出错。
我想我找到了我理解中的主要问题。主要问题是,在距离树的根级别 'd' 的给定级别,我可以有多个匹配项,例如"lot"和"dog"与"dot"改造后达到的水平相同。
在每个级别,我都必须排完队列,否则我计算的距离将变得不正确。
因此,当我将代码更改为以下内容时(请参阅代码中的注释 Process all items in queue which contains words on same level
),算法变得更好了。至少对于许多测试用例来说更好,包括这个问题中给出的测试用例。
感谢大家审阅代码。 :)
var ladderLength = function(beginWord, endWord, wordList) {
wordList = new Set(wordList);
var queue = [], distance = 1, i, j, len;
len = beginWord.length;
queue.push(beginWord);
while (queue.length > 0) {
// Process all items in queue which contains words on same level
for (var k=0; k<queue.length; k++) {
var currentWord = queue.shift();
if (currentWord === endWord) {
return distance;
}
for (i = 0; i < len; i++) {
var tempCh = currentWord[i];
for (j = 'a'; j <= 'z'; j = String.fromCharCode(j.charCodeAt(0)+1)) {
if (j !== tempCh) {
currentWord = currentWord.replaceAt(i,j);
if (wordList.has(currentWord)) {
wordList.delete(currentWord);
queue.push(currentWord);
}
}
}
currentWord = currentWord.replaceAt(i, tempCh);
}
}
distance++;
}
return 0;
};
String.prototype.replaceAt=function(index, replacement) {
return this.substr(0, index) + replacement+ this.substr(index + replacement.length);
}
我正在尝试编写一个算法,该算法应该找到从给定的 beginWord 到 endWord 的最短转换路径,这样一个字母就可以一次更改。
测试用例
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log","cog"]
预期输出为 5,因为可以遵循长度为 5 的最短转换之一:
"hit" -> "hot" -> "dot" -> "dog" -> "cog"
在我的算法中,我使用队列遵循 BFS,对于每个单词,我用从 'a' 到 'z' 的所有字母替换它的每个字母,同时我检查结果单词是否存在于给定的词典中,即 wordList.
如果是,那我就把它推入队列,这样它也可以像最后一个字一样处理。否则,从队列中获取下一个条目,依此类推,直到队列为空。
现在,我的代码如下 returns hit -> hot -> dot -> lot -> dog -> log -> cog
,这是一个错误的输出。这主要是因为dot
和dog
错误地转换成了lot
。
lot
和 dog
以及一个与 dot
不同的字母,因此它们都被推入队列并稍后处理,这导致类似的问题 [= 的双重转换15=] 变成 log
和 cog
。
现在,这清楚地表明我遗漏了 BFS 和最短路径搜索的一些关键点。我如何决定我必须将 dot
转换为 dog
而不是 lot
以确保我按照最短路径到达预期目标,前提是两者都是有效的转换dot
.
这将帮助我理解和修复我的代码。
var ladderLength = function(beginWord, endWord, wordList) {
wordList = new Set(wordList);
var str = [beginWord];
var queue = [], distance = 0, i, j, len;
len = beginWord.length;
queue.push(beginWord);
while (queue.length > 0) {
var currentWord = queue.shift();
if (currentWord === endWord) {
console.log(str.join(" -> "));
return distance + 1;
}
for (i = 0; i < len; i++) {
var tempCh = currentWord[i];
for (j = 'a'; j <= 'z'; j = String.fromCharCode(j.charCodeAt(0)+1)) {
currentWord = currentWord.replaceAt(i,j);
if (wordList.has(currentWord)) {
distance++;
wordList.delete(currentWord);
str.push(currentWord);
queue.push(currentWord);
}
}
currentWord = currentWord.replaceAt(i, tempCh);
}
}
return 0;
};
String.prototype.replaceAt=function(index, replacement) {
return this.substr(0, index) + replacement+ this.substr(index + replacement.length);
}
您可以在转换字符串的同时进行一些额外的处理以获得正确的输出。在替换字母之前,将要替换的字符 (i)
与将取代它的字符 (j)
.
为每次迭代保留一个标志变量flag
,并检查新字符j
是否会更接近EndWord
中相应位置的字符。如果它正在靠近而不是远离(例如,'d' vs 'l' for 'c' in cog),并且存在于 WordList
中,进行替换并设置 flag = true
。如果在与角色的距离相同的情况下也可以进行另一个转换,请检查标志,如果为真,则跳过它,否则进行转换。
希望对您有所帮助。
I replace each of its letter with all alphabets
表示您进行了太多有效性检查。
我建议您只用 valid 字母替换每个字母。例如"hit"中的i只能用o代替:"hot","dot","dog","lot","log","cog".
这将使程序更高效,更不容易出错。
我想我找到了我理解中的主要问题。主要问题是,在距离树的根级别 'd' 的给定级别,我可以有多个匹配项,例如"lot"和"dog"与"dot"改造后达到的水平相同。
在每个级别,我都必须排完队列,否则我计算的距离将变得不正确。
因此,当我将代码更改为以下内容时(请参阅代码中的注释 Process all items in queue which contains words on same level
),算法变得更好了。至少对于许多测试用例来说更好,包括这个问题中给出的测试用例。
感谢大家审阅代码。 :)
var ladderLength = function(beginWord, endWord, wordList) { wordList = new Set(wordList);
var queue = [], distance = 1, i, j, len;
len = beginWord.length;
queue.push(beginWord);
while (queue.length > 0) {
// Process all items in queue which contains words on same level
for (var k=0; k<queue.length; k++) {
var currentWord = queue.shift();
if (currentWord === endWord) {
return distance;
}
for (i = 0; i < len; i++) {
var tempCh = currentWord[i];
for (j = 'a'; j <= 'z'; j = String.fromCharCode(j.charCodeAt(0)+1)) {
if (j !== tempCh) {
currentWord = currentWord.replaceAt(i,j);
if (wordList.has(currentWord)) {
wordList.delete(currentWord);
queue.push(currentWord);
}
}
}
currentWord = currentWord.replaceAt(i, tempCh);
}
}
distance++;
}
return 0;
};
String.prototype.replaceAt=function(index, replacement) {
return this.substr(0, index) + replacement+ this.substr(index + replacement.length);
}