数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学使用JavaScript验证Boggle单词
问题
Boggle棋盘是一个二维字符数组，例如：
const board = [ ["I","L","A","W"], ["B","N","G","E"], ["I","U","A","O"], ["A","S","R","L"] ];
我们需要编写一个JavaScript函数，该函数接收Boggle棋盘和一个字符串作为输入，并检查该字符串是否为Boggle棋盘中的有效猜测。有效的猜测是可以通过连接相邻单元格（水平、垂直或对角线）形成的字符串，并且不会重复使用任何先前使用的单元格。
例如，在上图棋盘中，“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));代码解释
我们采取的步骤如下：
我们扫描二维数组以查找第一个字母的出现位置。
然后我们将{位置，索引}推入队列，当队列非空时，我们将第一个对象弹出。
然后我们查找所有方向。如果单元格中的字母与单词中的字母匹配，并且单元格未被重复使用，则我们更新{位置，索引}并将其添加到队列中；否则，我们丢弃该对象。当找到匹配项或所有方向都未找到匹配项时，我们停止。
输出
true
更新于：2021年4月19日
433次浏览
广告