Word Search

79. 单词搜索

分析

遍历网格：
- 使用双层循环遍历网格中的每个字符
- 如果发现当前字符和目标单词的首字符匹配，则从这个位置开始进行深度优先搜索
dfs()：
- 检查当前网格字符是否匹配目标单词的当前字符
- 如果匹配，检查是否已经完成整个单词的匹配
- 临时将当前字符标记为已访问（用 * 替代），以防止重复访问
- 按照上下左右四个方向继续搜索，递归调用 dfs()
- 如果所有方向都无法匹配剩余字符，则将当前字符还原，返回 false
返回结果：
- 如果某次 DFS 找到了目标单词，则立即返回 true
- 如果遍历完网格后仍未找到匹配，返回 false

时间复杂度

每个网格单元都可能作为起点触发一次深度优先搜索。
搜索深度最多为 word.length。
最坏情况下，搜索路径为网格大小 m × n 的全部单元

时间复杂度为 O(m × n × 4^l)，其中 l 是单词的长度

空间复杂度

递归栈的深度最多为单词的长度 l，空间复杂度为 O(l)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45


class Solution
{
public:
    bool exist(vector<vector<char>>& board, string word)
    {
      // 遍历整个网格
      for (int i = 0; i < board.size(); ++ i)
        for (int j = 0; j < board[0].size(); ++ j)
          // 如果从某个位置开始匹配成功，直接返回true
          if (dfs(board, word, 0, i, j))
            return true;
      return false; // 如果遍历完所有位置都未找到，返回false
    }

    bool dfs(std::vector<std::vector<char>>& board, std::string& word, int u, int x, int y)
    {
      // 当前字符与目标单词的字符不匹配
      if (board[x][y] != word[u])
        return false;

      // 匹配到单词的最后一个字符，返回true
      if (u == word.size() - 1)
        return true;

      // 标记当前字符已访问
      char temp = board[x][y];
      board[x][y] = '*';
      int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0}; // 四个方向数组

      for (int i = 0; i < 4; ++ i)
      {
        int a = x + dx[i], b = y + dy[i];
        // 确保新的位置不越界且未访问
        if (a < 0 || a >= board.size() || b < 0 || b >= board[0].size() || board[a][b] == '*')
         continue;
        // 递归检查下一字符是否匹配
        if (dfs(board, word, u + 1, a, b))
          return true;
      }

      // 恢复当前字符，继续尝试其他路径
      board[x][y] = temp;
      return false;
    }
};