بالنظر إلى لوحة ثنائية الأبعاد وكلمة، ابحث عما إذا كانت الكلمة موجودة في الشبكة. يمكن بناء الكلمة من حروف الخلايا المجاورة بشكل متسلسل، حيث تكون الخلايا 'المجاورة' متجاورة أفقيًا أو رأسيًا.
الشرح: يتطلب هذا بحثًا أول بالعمق (DFS) مع التراجع. كرر خلال كل خلية. إذا تطابقت الخلية مع الحرف الأول من الكلمة، ابدأ DFS. تتحقق دالة DFS من الجيران، مع التأكد من أنها تتطابق مع الحرف التالي ولم يتم زيارتها في المسار الحالي. إذا فشل المسار، تراجع عن طريق إلغاء تحديد الخلية.
function exist(board, word) {
const rows = board.length;
const cols = board[0].length;
function dfs(r, c, index) {
if (index === word.length) return true; // تم العثور على الكلمة
if (r < 0 || c < 0 || r >= rows || c >= cols || board[r][c] !== word[index]) {
return false;
}
const temp = board[r][c];
board[r][c] = '#'; // وضع علامة تم الزيارة
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; // التراجع
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