একটি 2D বোর্ড এবং একটি শব্দ দেওয়া হলে, শব্দটি গ্রিডে বিদ্যমান কিনা তা খুঁজুন। শব্দটি ক্রমানুসারে সংলগ্ন কোষগুলির অক্ষর থেকে তৈরি করা যেতে পারে, যেখানে 'সংলগ্ন' কোষগুলি অনুভূমিকভাবে বা উল্লম্বভাবে প্রতিবেশী।
ব্যাখ্যা: এর জন্য ব্যাকট্র্যাকিং সহ একটি ডেপথ ফার্স্ট সার্চ (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