题目描述给定一个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解题思路方法一回溯 DFS核心思路从每个格子出发尝试匹配word的第一个字符然后向四个方向扩展。匹配成功继续匹配下一个字符匹配失败回溯换方向越界或已访问跳过关键操作标记已访问把当前格子改成特殊字符如#避免重复使用四个方向上、下、左、右回溯恢复格子的原字符具体过程示例board [[A,B,C,E],[S,F,C,S],[A,D,E,E]],word ABCCED路径: A → B → C → C → E → D (0,0) → (0,1) → (0,2) → (1,2) → (2,2) → (2,1) A B C E S F C S A D E E代码实现class Solution { public: bool exist(vectorvectorchar board, string word) { int m board.size(), n board[0].size(); for (int i 0; i m; i) { for (int j 0; j n; j) { if (dfs(board, word, i, j, 0)) { return true; } } } return false; } private: bool dfs(vectorvectorchar board, string word, int i, int j, int index) { // 匹配完成 if (index word.size()) return true; // 越界或不匹配 if (i 0 || i board.size() || j 0 || j board[0].size() || board[i][j] ! word[index]) { return false; } // 标记已访问 char temp board[i][j]; board[i][j] #; // 四个方向搜索 bool found dfs(board, word, i 1, j, index 1) || dfs(board, word, i - 1, j, index 1) || dfs(board, word, i, j 1, index 1) || dfs(board, word, i, j - 1, index 1); // 恢复 board[i][j] temp; return found; } };复杂度分析设m × n是网格大小L是单词长度。维度复杂度说明时间复杂度O(m × n × 3^L)每个格子出发每步最多3个方向不回头空间复杂度O(L)递归栈深度为什么是 3^L 而不是 4^L因为每次不能走回头路已访问的格子被标记所以每步最多3个方向。关键细节1. 为什么用#标记已访问避免重复使用同一个格子比额外维护visited数组更省空间回溯时恢复原字符2. 为什么四个方向用||连接只要有一个方向能找到就返回true。||有短路特性找到后不再继续搜索。3. 为什么先判断index word.size()当index等于单词长度时说明所有字符都匹配完了返回true。4. 为什么越界判断放在前面避免访问越界的内存同时判断字符是否匹配。方法二用visited数组代码实现class Solution { public: bool exist(vectorvectorchar board, string word) { int m board.size(), n board[0].size(); vectorvectorbool visited(m, vectorbool(n, false)); for (int i 0; i m; i) { for (int j 0; j n; j) { if (dfs(board, word, visited, i, j, 0)) { return true; } } } return false; } private: bool dfs(vectorvectorchar board, string word, vectorvectorbool visited, int i, int j, int index) { if (index word.size()) return true; if (i 0 || i board.size() || j 0 || j board[0].size() || visited[i][j] || board[i][j] ! word[index]) { return false; } visited[i][j] true; bool found dfs(board, word, visited, i 1, j, index 1) || dfs(board, word, visited, i - 1, j, index 1) || dfs(board, word, visited, i, j 1, index 1) || dfs(board, word, visited, i, j - 1, index 1); visited[i][j] false; return found; } };缺点需要额外 O(m × n) 空间。两种方法对比方法时间复杂度空间复杂度推荐度原地标记O(m × n × 3^L)O(L)⭐⭐⭐⭐⭐visited 数组O(m × n × 3^L)O(m × n L)⭐⭐⭐⭐总结要点说明核心思想从每个格子出发DFS 匹配单词关键操作标记已访问 → 四方向搜索 → 恢复终止条件index word.size()返回 true时间复杂度O(m × n × 3^L)空间复杂度O(L)