【每日一题】LeetCode 79. 单词搜索 TypeScript

给定一个m x n二维字符网格board和一个字符串单词word。如果word存在于网格中返回true否则返回false。单词必须按照字母顺序通过相邻的单元格内的字母构成其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。示例 1输入board [[A,B,C,E],[S,F,C,S],[A,D,E,E]], word ABCCED输出true示例 2输入board [[A,B,C,E],[S,F,C,S],[A,D,E,E]], word SEE输出true示例 3输入board [[A,B,C,E],[S,F,C,S],[A,D,E,E]], word ABCB输出false提示m board.lengthn board[i].length1 m, n 61 word.length 15board和word仅由大小写英文字母组成function exist(board: string[][], word: string): boolean { const m board.length; const n board[0].length; const visited: boolean[][] Array.from({ length: m }, () Array(n).fill(false)); const directions: [number, number][] [ [1, 0], [-1, 0], [0, 1], [0, -1] ]; const dfs (row: number, col: number, index: number): boolean { // 已匹配完所有字符 if (index word.length) return true; // 边界检查 / 已访问 / 字符不匹配 if (row 0 || row m || col 0 || col n) return false; if (visited[row][col]) return false; if (board[row][col] ! word[index]) return false; // 标记已访问 visited[row][col] true; // 向四个方向继续搜索 for (const [dr, dc] of directions) { if (dfs(row dr, col dc, index 1)) { return true; } } // 回溯取消标记 visited[row][col] false; return false; }; // 从每个单元格作为起点尝试 for (let i 0; i m; i) { for (let j 0; j n; j) { if (dfs(i, j, 0)) { return true; } } } return false; }