时间轴

2025-11-30

init

题目：

P79 单词搜索

https://leetcode.cn/problems/word-search/description/?envType=study-plan-v2&envId=top-interview-150

回溯，遍历每个起点，注意访问过的要在board做标记以防重复访问。

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <vector>
#include <string>
using std::vector;
using std::string;

const int next_offset[4][2] = { { -1, 0 }, { 0, -1 }, { 1, 0 }, { 0, 1 } };

class Solution {
	bool res;
	bool on_board(int i, int j, int m, int n)
	{
		return (i >= 0 && i < m && j >= 0 && j < n);
	}
	void backtrace(string &track, vector<vector<char> > &board, int curr_i, int curr_j, string word)
	{
		if (track.compare(word) == 0) {
			this->res = true;
			return;
		}

		char next = word[track.size()];
		int i, m = board.size(), n = board[0].size();
		int ni, nj;

		for (i = 0; i < 4; i++) {
			ni = curr_i + next_offset[i][0];
			nj = curr_j + next_offset[i][1];
			if (on_board(ni, nj, m, n) && board[ni][nj] == next) {
				board[ni][nj] = '#';
				track.push_back(next);
				backtrace(track, board, ni, nj, word);
				track.pop_back();
				board[ni][nj] = next;
			}
		}
	}

    public:
	bool exist(vector<vector<char> > &board, string word)
	{
		this->res = false;

		int i, j, m = board.size(), n = board[0].size();
		char first_ch = word[0];
		string track;
		track.push_back(first_ch);
		for (i = 0; i < m; i++) {
			for (j = 0; j < n; j++) { //遍历每个起点
				if (board[i][j] == first_ch) {
					board[i][j] = '#';
					backtrace(track, board, i, j, word);
					board[i][j] = first_ch;
				}
				if (this->res) {
					return true;
				}
			}
		}
		return false;
	}
};