使用 JavaScript 验证一个令人难以置信的词
问题
Boggle板是单个字符的二维数组，例如-
const board = [ ["I","L","A","W"], ["B","N","G","E"], ["I","U","A","O"], ["A","S","R","L"] ];
我们需要编写一个JavaScript函数，它接受boggleboard和一个字符串，并检查该字符串是否是boggleboard中的有效猜测。有效的猜测是可以通过连接相邻单元格（水平、垂直或对角线）而不重复使用任何以前使用的单元格而形成的字符串。
例如，在上面的棋盘中，“LINGO”和“ILNBIA”都是有效的猜测，而“BUNGIE”和“SINUS”则不是。
示例
以下是代码-
const board = [
["I","L","A","W"],
["B","N","G","E"],
["I","U","A","O"],
["A","S","R","L"]
];
const guess = 'BINGO';
const checkWord = (board = [], guess = '') => {
const numRows = board.length;
const numCols = board[0].length;
let queue = board.reduce((acc, row, i) => {
row.forEach((x, j) => {
if (x === guess[0]) {
acc.push( { pos: {r: i, c: j} , nextIndex: 1, path: [numCols*i + j ] } );
}
});
return acc;
}, []);
let exploreWord = (obj, queue) => {
let allMoves = [ {r: obj.pos.r - 1, c: obj.pos.c },
{r: obj.pos.r + 1, c: obj.pos.c },
{r: obj.pos.r, c: obj.pos.c - 1 },
{r: obj.pos.r, c: obj.pos.c + 1 },
{r: obj.pos.r - 1, c: obj.pos.c - 1 },
{r: obj.pos.r - 1, c: obj.pos.c + 1 },
{r: obj.pos.r + 1, c: obj.pos.c - 1 },
{r: obj.pos.r + 1, c: obj.pos.c + 1 }];
allMoves.forEach((o) => {
let index = numCols *o.r+ o.c;
if (o.r >= 0 &&o.r< numRows &&o.c>= 0 &&o.c< numCols) {
if (board[o.r][o.c] === guess[obj.nextIndex] && !obj.path.includes(index)) {
let cloneObj = JSON.parse(JSON.stringify(obj));
cloneObj.pos = { r: o.r, c:o.c};
cloneObj.nextIndex += 1;
cloneObj.path.push(index);
queue.push(cloneObj);
}
}
});
};
while (queue.length > 0) {
let obj = queue.shift();
if (obj.nextIndex === guess.length) {
return true;
}
exploreWord(obj, queue);
}
return false;
};
console.log(checkWord(board, guess));代码说明
我们采取的步骤是-
我们扫描二维数组以找到第一个字母的出现
然后我们把{位置，索引}推入队列，当队列不为空时，我们弹出第一个对象
然后我们寻找所有方向。如果单元格中的字母与单词中的字母匹配并且单元格没有被重用，我们更新{position,index}并附加到队列中，否则我们丢弃该对象并在找到匹配项或全部不匹配时停止。
输出结果
true