单词搜索

GitHub跳转原题关系图返回列表

DFS 搜索路径，进入格子后标记已访问防止复用，递归后恢复现场，四方向扩展匹配下一个字符。

OJ: leetcodecn

题目 ID: word-search

难度:普及+/提高

标签:回溯搜索DFS网格

日期: 2026-07-29 11:30

目录

  1. 题意
  2. 思路
  3. 代码
  4. 复杂度
  5. 总结

题意

在 m x n 字符网格中判断是否存在一条路径，按相邻（水平/垂直）单元格依次拼出给定单词 word。同一个单元格不能重复使用。

思路

最直接的思路是从每个格子出发尝试 DFS 匹配单词：

cpp
// brute.cpp：小数据暴力解，DFS 搜索路径，进入格子后标记、递归、恢复现场必须成对。
#include <bits/stdc++.h>
using namespace std;

int m, n;
char grid[10][10];
string word;
bool vis[10][10];

bool dfs(int i, int j, int idx) {
    if (idx == (int)word.size())
        return true;
    if (i < 0 || i >= m || j < 0 || j >= n || vis[i][j] || grid[i][j] != word[idx])
        return false;
    vis[i][j] = true;
    bool ok = dfs(i - 1, j, idx + 1) || dfs(i + 1, j, idx + 1) || dfs(i, j - 1, idx + 1) ||
              dfs(i, j + 1, idx + 1);
    vis[i][j] = false;
    return ok;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> m >> n;
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            cin >> grid[i][j];
    cin >> word;
    bool found = false;
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            if (dfs(i, j, 0)) {
                found = true;
                break;
            }
    cout << (found ? 1 : 0) << '\n';
    return 0;
}

brute.cpp 用独立的 vis 数组标记已访问格子，逻辑与 main.cpp 相同（本题 DFS 本身就是最优方案，因为必须逐字符尝试所有路径）。

关键实现要点：

  • 进入格子后立即标记（vis[i][j] = true 或 board[i][j] = '#'），防止路径中重复使用同一格子。
  • 递归返回后必须恢复现场（vis[i][j] = false 或 board[i][j] = tmp），否则后续从其他起点出发的搜索会看到被污染的网格。
  • 匹配失败的条件要全部检查：越界、已访问、字符不匹配。

代码

cpp
#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    bool exist(vector<vector<char>> &board, string word) {
        int m = board.size(), n = board[0].size();
        function<bool(int, int, int)> dfs = [&](int i, int j, int idx) {
            if (idx == (int)word.size())
                return true;
            if (i < 0 || i >= m || j < 0 || j >= n || board[i][j] != word[idx])
                return false;
            char tmp = board[i][j];
            board[i][j] = '#';
            bool ok = dfs(i - 1, j, idx + 1) || dfs(i + 1, j, idx + 1) || dfs(i, j - 1, idx + 1) ||
                      dfs(i, j + 1, idx + 1);
            board[i][j] = tmp;
            return ok;
        };
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (dfs(i, j, 0))
                    return true;
        return false;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int m, n;
    cin >> m >> n;
    vector<vector<char>> b(m, vector<char>(n));
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            cin >> b[i][j];
    string w;
    cin >> w;
    cout << Solution().exist(b, w) << '\n';
    return 0;
}
python
#!/usr/bin/env python3
from typing import List


class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        m, n = len(board), len(board[0])

        def dfs(i, j, idx):
            if idx == len(word):
                return True
            if i < 0 or i >= m or j < 0 or j >= n or board[i][j] != word[idx]:
                return False
            tmp, board[i][j] = board[i][j], "#"
            ok = (
                dfs(i - 1, j, idx + 1)
                or dfs(i + 1, j, idx + 1)
                or dfs(i, j - 1, idx + 1)
                or dfs(i, j + 1, idx + 1)
            )
            board[i][j] = tmp
            return ok

        for i in range(m):
            for j in range(n):
                if dfs(i, j, 0):
                    return True
        return False


def main():
    m, n = map(int, input().split())
    b = [input().split() for _ in range(m)]
    w = input().strip()
    print(Solution().exist(b, w))


if __name__ == "__main__":
    main()

复杂度

  • 时间复杂度：最坏 O(m⋅n⋅4k)O(m \cdot n \cdot 4^k)，其中 k=len(word)k = \text{len(word)}。每个起点最多 4 方向扩展 kk 层。
  • 空间复杂度：O(k)O(k)，递归栈深度为单词长度。

总结

网格路径搜索的核心是"标记→递归→恢复"三步必须成对。本题用临时修改网格值或 vis 数组来标记访问状态，递归返回时恢复原值，保证后续搜索不受影响。