javascript - 为什么我的 BFS 算法没有返回预期的最短路径？

Question

我正在尝试编写一种算法，该算法应该找到从给定 beginWord 到 endWord 的最短转换路径，以便一次可以更改一个字母。

测试用例

beginWord = "hit"

endWord = "cog"

wordList = ["hot","dot","dog","lot","log","cog"]

预期输出为 5，因为可以遵循长度为 5 的最短转换之一:

"hit"-> "hot"-> "dot"-> "dog"-> "cog"

在我的算法中，我使用队列遵循 BFS，对于每个单词，我用从“a”到“z”的所有字母替换它的每个字母，同时我检查给定字典中是否存在结果单词，即wordList.

如果是，那么我将它插入队列，这样它也可以像最后一个词一样被处理。否则，从队列中取出下一个条目，依此类推，直到队列为空。

现在，我下面给出的代码返回 hit -> hot -> dot -> lot -> dog -> log -> cog，这是一个错误的输出。这主要是因为dot错误地转换成了lot和dog。

lot 和 dog 以及一个与 dot 不同的字母，因此它们都被插入队列并稍后处理，结果类似lot 到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);
}

Answer 1

您可以在转换字符串的同时进行一些额外的处理以获得正确的输出。在替换字母之前，比较将被替换的字符 (i)与将取代它的 Angular 色 (j) .

保留一个标志变量flag对于每次迭代并检查新字符是否为 j会更接近EndWord中相应位置的字符.如果它正在靠近而不是离开(例如，'d' vs 'l' for 'c' in cog)，并且存在于 WordList 中, 进行替换并设置 flag = true .如果在与 Angular 色的距离相同的情况下也可以进行另一个转换，则检查标志，如果为真，则跳过它，否则进行转换。

希望这对您有所帮助。