2B bir tahta ve bir kelime verildiğinde, kelimenin ızgarada var olup olmadığını bulun. Kelime, bitişik hücrelerin harflerinden oluşturulabilir, burada 'bitişik' hücreler yatay veya dikey olarak komşudur.
Açıklama: Bu, geri izlemeli bir Derinlik Öncelikli Arama (DFS) gerektirir. Her hücre boyunca yineleyin. Bir hücre kelimenin ilk harfiyle eşleşiyorsa, bir DFS başlatın. DFS fonksiyonu komşuları kontrol eder, bir sonraki harfle eşleşmelerini ve mevcut yolda ziyaret edilmemiş olmalarını sağlar. Bir yol başarısız olursa, hücrenin işaretini kaldırarak geri izleyin.
function exist(board, word) {
const rows = board.length;
const cols = board[0].length;
function dfs(r, c, index) {
if (index === word.length) return true; // Kelime bulundu
if (r < 0 || c < 0 || r >= rows || c >= cols || board[r][c] !== word[index]) {
return false;
}
const temp = board[r][c];
board[r][c] = '#'; // Ziyaret edildi olarak işaretle
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; // Geri izleme
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