代码随想录

# 79. 单词搜索

力扣题目链接 (opens new window)

# 题目描述

给定一个 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
1
2

示例 2：

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
输出：true
1
2

示例 3：

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
输出：false
1
2

提示：

  • m == board.length
  • n = board[i].length
  • 1 <= m, n <= 6
  • 1 <= word.length <= 15
  • board 和 word 仅由大小写英文字母组成

进阶：你可以使用搜索剪枝的技术来优化解决方案，使其在 board 更大的情况下可以更快解决问题？

# 思路

这道题一看就是回溯算法的经典应用。

在二维网格中搜索路径，需要尝试四个方向，如果当前路径不行，就回退，尝试其他路径。

# 回溯三部曲

1. 递归函数参数

需要传入：

  • 当前坐标(i, j)
  • 当前匹配到word的第几个字符index

2. 递归终止条件

  • 如果index == word.length()，说明所有字符都匹配成功，返回true
  • 如果当前坐标越界，或者当前字符不匹配，或者当前位置已经访问过，返回false

3. 单层搜索逻辑

从当前位置出发，尝试上下左右四个方向：

  • 标记当前位置为已访问
  • 递归搜索下一个字符
  • 如果找到了，直接返回true
  • 如果没找到，回溯：取消当前位置的访问标记

# 怎么标记访问过的位置？

有两种方法：

  1. 用一个visited数组记录
  2. 直接修改board，把访问过的字符改成特殊字符（比如'#'），回溯时再改回来

方法2更省空间，代码中采用这种方式。

# 从哪里开始搜索？

需要遍历整个网格，把每个位置都作为起点尝试一遍。

# 模拟过程

以 board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED" 为例：

从 (0,0) 开始搜索，找到完整路径：

  • (0,0) A → (0,1) B → (0,2) C → (1,2) C → (2,2) E → (2,1) D

关键点：

  1. 回溯三步：标记（改为#）→ 递归搜索 → 恢复
  2. 四个方向搜索：上下左右
  3. 用修改原数组的方式标记访问，省空间

# 解题代码

class Solution {
private:
    int m, n;
    
    bool backtracking(vector<vector<char>>& board, string& word, int i, int j, int index) {
        // 递归终止条件：所有字符都匹配成功
        if (index == word.size()) return true;
        
        // 边界检查 + 字符不匹配 + 已访问过
        if (i < 0 || i >= m || j < 0 || j >= n || 
            board[i][j] != word[index] || board[i][j] == '#') {
            return false;
        }
        
        // 标记当前位置为已访问
        char temp = board[i][j];
        board[i][j] = '#';
        
        // 向四个方向搜索
        bool found = backtracking(board, word, i + 1, j, index + 1) ||  // 下
                     backtracking(board, word, i - 1, j, index + 1) ||  // 上
                     backtracking(board, word, i, j + 1, index + 1) ||  // 右
                     backtracking(board, word, i, j - 1, index + 1);    // 左
        
        // 回溯：恢复现场
        board[i][j] = temp;
        
        return found;
    }
    
public:
    bool exist(vector<vector<char>>& board, string word) {
        m = board.size();
        n = board[0].size();
        
        // 遍历每个位置作为起点
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (backtracking(board, word, i, j, 0)) {
                    return true;
                }
            }
        }
        
        return false;
    }
};
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
46
47

# 复杂度分析

  • 时间复杂度：O(m × n × 4^L)，其中L是word的长度。最坏情况下，每个位置都要尝试，每次尝试最多向四个方向递归L层
  • 空间复杂度：O(L)，递归调用栈的深度

# 其他语言

# Python3

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        m, n = len(board), len(board[0])
        
        def backtracking(i, j, index):
            # 递归终止条件：所有字符都匹配成功
            if index == len(word):
                return True
            
            # 边界检查 + 字符不匹配 + 已访问过
            if i < 0 or i >= m or j < 0 or j >= n or \
               board[i][j] != word[index] or board[i][j] == '#':
                return False
            
            # 标记当前位置为已访问
            temp = board[i][j]
            board[i][j] = '#'
            
            # 向四个方向搜索
            found = (backtracking(i + 1, j, index + 1) or  # 下
                     backtracking(i - 1, j, index + 1) or  # 上
                     backtracking(i, j + 1, index + 1) or  # 右
                     backtracking(i, j - 1, index + 1))    # 左
            
            # 回溯：恢复现场
            board[i][j] = temp
            
            return found
        
        # 遍历每个位置作为起点
        for i in range(m):
            for j in range(n):
                if backtracking(i, j, 0):
                    return True
        
        return False
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

# Java

class Solution {
    private int m, n;
    
    public boolean exist(char[][] board, String word) {
        m = board.length;
        n = board[0].length;
        
        // 遍历每个位置作为起点
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (backtracking(board, word, i, j, 0)) {
                    return true;
                }
            }
        }
        
        return false;
    }
    
    private boolean backtracking(char[][] board, String word, int i, int j, int index) {
        // 递归终止条件：所有字符都匹配成功
        if (index == word.length()) return true;
        
        // 边界检查 + 字符不匹配 + 已访问过
        if (i < 0 || i >= m || j < 0 || j >= n || 
            board[i][j] != word.charAt(index) || board[i][j] == '#') {
            return false;
        }
        
        // 标记当前位置为已访问
        char temp = board[i][j];
        board[i][j] = '#';
        
        // 向四个方向搜索
        boolean found = backtracking(board, word, i + 1, j, index + 1) ||  // 下
                        backtracking(board, word, i - 1, j, index + 1) ||  // 上
                        backtracking(board, word, i, j + 1, index + 1) ||  // 右
                        backtracking(board, word, i, j - 1, index + 1);    // 左
        
        // 回溯：恢复现场
        board[i][j] = temp;
        
        return found;
    }
}
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

# Go

func exist(board [][]byte, word string) bool {
    m, n := len(board), len(board[0])
    
    var backtracking func(i, j, index int) bool
    backtracking = func(i, j, index int) bool {
        // 递归终止条件：所有字符都匹配成功
        if index == len(word) {
            return true
        }
        
        // 边界检查 + 字符不匹配 + 已访问过
        if i < 0 || i >= m || j < 0 || j >= n || 
           board[i][j] != word[index] || board[i][j] == '#' {
            return false
        }
        
        // 标记当前位置为已访问
        temp := board[i][j]
        board[i][j] = '#'
        
        // 向四个方向搜索
        found := backtracking(i+1, j, index+1) ||  // 下
                 backtracking(i-1, j, index+1) ||  // 上
                 backtracking(i, j+1, index+1) ||  // 右
                 backtracking(i, j-1, index+1)     // 左
        
        // 回溯：恢复现场
        board[i][j] = temp
        
        return found
    }
    
    // 遍历每个位置作为起点
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if backtracking(i, j, 0) {
                return true
            }
        }
    }
    
    return false
}
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

# JavaScript

var exist = function(board, word) {
    const m = board.length;
    const n = board[0].length;
    
    const backtracking = (i, j, index) => {
        // 递归终止条件：所有字符都匹配成功
        if (index === word.length) return true;
        
        // 边界检查 + 字符不匹配 + 已访问过
        if (i < 0 || i >= m || j < 0 || j >= n || 
            board[i][j] !== word[index] || board[i][j] === '#') {
            return false;
        }
        
        // 标记当前位置为已访问
        const temp = board[i][j];
        board[i][j] = '#';
        
        // 向四个方向搜索
        const found = backtracking(i + 1, j, index + 1) ||  // 下
                      backtracking(i - 1, j, index + 1) ||  // 上
                      backtracking(i, j + 1, index + 1) ||  // 右
                      backtracking(i, j - 1, index + 1);    // 左
        
        // 回溯：恢复现场
        board[i][j] = temp;
        
        return found;
    };
    
    // 遍历每个位置作为起点
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (backtracking(i, j, 0)) {
                return true;
            }
        }
    }
    
    return false;
};
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

# 与代码随想录联系

这道题是回溯算法在二维网格中的应用。

我在代码随想录回溯章节里，详细讲解了回溯三部曲，建议录友们先看代码随想录回溯章节，特别是77.组合、46.全排列这些基础题。

本题的关键点：

  1. 回溯模板：标记→递归→恢复
  2. 四个方向搜索：上下左右
  3. visited标记：用修改原数组的方式省空间

另外，题目提到的剪枝优化，可以先统计word中每个字符出现的次数，如果board中某个字符不够，直接返回false。这样可以提前终止搜索，提高效率。

上次更新：: 10/25/2026, 10:24:40 PM

评论

验证登录状态...