एक 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