LC79. 单词搜索

题目描述

给定一个 m x n 二维字符网格 board 和一个字符串单词 word，如果 word 存在于网格中，返回 true；否则返回 false。单词必须按照字母顺序，通过相邻的单元格（水平或垂直）构成，同一个单元格内的字母不允许重复使用。

示例： 输入：board = [['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], word = 'ABCCED' 输出：true

思路解析

核心思路：深度优先搜索（DFS）+ 回溯。遍历网格每个单元格，以该单元格为起点，尝试匹配 word 的第一个字符，然后递归地向四个方向搜索下一个字符，同时标记已访问的单元格（避免重复使用）。如果某条路径匹配失败，则回溯（取消标记）。 关键点： 1. 递归终止条件：当已匹配的字符数等于 word 长度时，返回 true。 2. 边界检查：索引越界或当前字符不匹配时，返回 false。 3. 使用临时标记（如将 board[i][j] 改为 '#'）代替 visited 数组，节省空间。