Gegeven een 2D-bord en een woord, zoek of het woord bestaat in het raster. Het woord kan worden geconstrueerd uit letters van opeenvolgend aangrenzende cellen, waarbij 'aangrenzend' cellen horizontaal of verticaal naast elkaar zijn.
Uitleg: Dit vereist een Depth First Search (DFS) met backtracking. Itereer door elke cel. Als een cel overeenkomt met de eerste letter van het woord, start dan een DFS. De DFS-functie controleert buren, en zorgt ervoor dat ze overeenkomen met de volgende letter en niet zijn bezocht in het huidige pad. Als een pad mislukt, backtrack dan door de cel ongedaan te maken.
function exist(board, word) {
const rows = board.length;
const cols = board[0].length;
function dfs(r, c, index) {
if (index === word.length) return true; // Woord gevonden
if (r < 0 || c < 0 || r >= rows || c >= cols || board[r][c] !== word[index]) {
return false;
}
const temp = board[r][c];
board[r][c] = '#'; // Markeren als bezocht
const found = dfs(r + 1, c, index + 1) ||
dfs(r - 1, c, index + 1) ||
dfs(r, c + 1, index + 1) ||
dfs(r, c - 1, index + 1);
board[r][c] = temp; // Backtrack
return found;
}
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
if (board[r][c] === word[0] && dfs(r, c, 0)) {
return true;
}
}
}
return false;
}
const board = [['A','B','C','E'],['S','F','C','S'],['A','D','E','E']];
console.log(exist(board, 'ABCCED')); // true
console.log(exist(board, 'SEE')); // true
console.log(exist(board, 'ABCB')); // false