JavaScript 中的词搜索 II 算法

Question

我正在尝试为 Word Search II 问题创建自己的解决方案（请不要向我发送与其他人的解决方案的链接，我正在尝试了解我的代码中有什么问题）。

问题：给定一个二维板和字典中的单词列表，找到板上的所有单词。

每个单词必须由顺序相邻单元格的字母构成，其中“相邻”单元格是水平或垂直相邻的单元格。同一个字母单元格不能在一个单词中使用多次。

示例：

Input: 
board = [
  ['o','a','a','n'],
  ['e','t','a','e'],
  ['i','h','k','r'],
  ['i','f','l','v']
]
words = ["oath","pea","eat","rain"]

Output: ["eat","oath"]

我的解决方案：

var findWords = function(board, words) {
    
    let output = new Set();
    const initials = new Map();
    for(let i=0; i<words.length; i++) {
        let temp;
        if(initials.has(words[i][0]))
            temp = initials.get(words[i][0]);
        else
            temp = [];
        temp.push(words[i]);
        initials.set(words[i][0], temp);
    }
    
    const checkOrder = (row, col, word, tempWord, visited) => {
        if(row < 0 || row >= board.length || col < 0 || col >= board[row].length || board[row][col] !== word[tempWord.length])
            return;
        if(visited[row][col] === 1) return;
        
        tempWord += board[row][col];
        visited[row][col] = 1;
        if(tempWord === word)   output.add(word);            
        
        checkOrder(row, col+1, word, tempWord, visited);
        checkOrder(row, col-1, word, tempWord, visited);
        checkOrder(row+1, col, word, tempWord, visited);
        checkOrder(row-1, col, word, tempWord, visited);
    }
    
    for(let i=0; i<board.length; i++) {
        for(let j=0; j<board[i].length; j++) {
            if(initials.has(board[i][j])) {
                // might form a word
                const listWords = initials.get(board[i][j]);
                for(let k=0; k<listWords.length; k++) {
                    const visited = new Array(board.length).fill(0).map(() => new Array(board[0].length).fill(0));
                    const word = listWords[k];
                    checkOrder(i, j, word, "", visited);
                }
            }
        }
    }
    
    return Array.from(output);
};

上面的输入效果很好。但是对于下面的输入：

board: [["a","b","c"],["a","e","d"],["a","f","g"]]
words: ["abcdefg","gfedcbaaa","eaabcdgfa","befa","dgc","ade"]

我的输出是： ["abcdefg","befa","gfedcbaaa"] 为什么我的代码不计算工作：“eaabcdgfa”？

谢谢

Answer 1

在您的第二个版块中搜索单词 eaabcdgfa 时，您的 depth-first 搜索算法：

从中间的e开始，标记为已访问，
在 centre-left 中找到一个 a，将其标记为已访问，
在 bottom-left 中找到一个 a，将其标记为已访问，
在 bottom-left 中的 a 旁边找不到 b，因此返回到第一个 a、
在 top-left 中找到另一个 a，将其标记为已访问，
在图板的边缘找到 b、c、d、g 和 f，将它们都标记为已访问，
无法添加左下角的a，因为它已被标记为已访问。

问题是 bottom-left 中的 a 被标记为已访问，尽管它不是从中心的 e 到 [=23] 的路线的一部分=] 在 bottom-centre.

如果想让visited数组记录当前对checkOrder的递归调用栈访问过的格子，那么需要将格子标记为之前不再访问过的格子checkOrder 结束。您可以通过添加行

        visited[row][col] = 0;

到 checkOrder 函数的底部，在对 checkOrder.

的所有递归调用下方

我对您的代码进行了此更改，它找到了单词 eaabcdfga。

JavaScript 中的词搜索 II 算法

Word Search II algorithm in JavaScript

javascript

arrays

depth-first-search