תיאור השאלה
Given an m x n grid of characters board and a string word, return true if word exists in the grid. The word must be built from letters of sequentially adjacent cells (horizontally or vertically), and the same cell may not be used more than once.
איך פותרים?
מכל תא שמתאים לאות הראשונה מריצים DFS. בכל צעד בודקים שהתא בגבולות ושהאות מתאימה, מסמנים את התא כמבוקר, ממשיכים לארבעת השכנים, ובחזרה משחזרים את האות (backtracking).
פתרון קוד
JavaScript
Python
function exist(board, word) {
const m = board.length;
const n = board[0].length;
function dfs(i, j, k) {
if (k === word.length) return true;
if (i < 0 || j < 0 || i >= m || j >= n || board[i][j] !== word[k]) return false;
const saved = board[i][j];
board[i][j] = "#";
const found =
dfs(i + 1, j, k + 1) || dfs(i - 1, j, k + 1) || dfs(i, j + 1, k + 1) || dfs(i, j - 1, k + 1);
board[i][j] = saved;
return found;
}
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (dfs(i, j, 0)) return true;
}
}
return false;
}
לעבור את ראיון העבודה הבא שלך בהצלחה
קורס דיגיטלי מקיף עם +25 שיעורים מעשיים, כשעתיים של וידאו, וליווי של מראיין בכיר.