时间轴

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;
	}
};

leetcode hot 100 rewirte, 经典回溯写法

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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <vector>
#include <string>

using std::vector;
using std::string;

class Solution {
    private:
        bool __exit(vector<vector<char> > &board, vector<vector<bool> > &visited, string word,
                    int curr_idx, int curri, int currj)
        {
                int m = board.size(), n = board[0].size();
                bool ret;

                if (curr_idx == word.size())
                        return true;

                // 上
                if (curri - 1 >= 0 && !visited[curri - 1][currj] &&
                    board[curri - 1][currj] == word[curr_idx]) {
                        visited[curri - 1][currj] = true;
                        ret = __exit(board, visited, word, curr_idx + 1, curri - 1, currj);
                        visited[curri - 1][currj] = false;
                        if (ret)
                                return true;
                }

                // 下
                if (curri + 1 < m && !visited[curri + 1][currj] &&
                    board[curri + 1][currj] == word[curr_idx]) {
                        visited[curri + 1][currj] = true;
                        ret = __exit(board, visited, word, curr_idx + 1, curri + 1, currj);
                        visited[curri + 1][currj] = false;
                        if (ret)
                                return true;
                }

                // 左
                if (currj - 1 >= 0 && !visited[curri][currj - 1] &&
                    board[curri][currj - 1] == word[curr_idx]) {
                        visited[curri][currj - 1] = true;
                        ret = __exit(board, visited, word, curr_idx + 1, curri, currj - 1);
                        visited[curri][currj - 1] = false;
                        if (ret)
                                return true;
                }

                // 下
                if (currj + 1 < n && !visited[curri][currj + 1] &&
                    board[curri][currj + 1] == word[curr_idx]) {
                        visited[curri][currj + 1] = true;
                        ret = __exit(board, visited, word, curr_idx + 1, curri, currj + 1);
                        visited[curri][currj + 1] = false;
                        if (ret)
                                return true;
                }

                return false;
        }

    public:
        bool exist(vector<vector<char> > &board, string word)
        {
                // m == board.length
                // n = board[i].length
                // 1 <= m, n <= 6
                // 1 <= word.length <= 15
                // board 和 word 仅由大小写英文字母组成

                int i, j, m = board.size(), n = board[0].size();
                vector<vector<bool> > visited(m, vector<bool>(n, false));

                for (i = 0; i < m; i++) {
                        for (j = 0; j < n; j++) {
                                if (board[i][j] == word[0]) {
                                        visited[i][j] = true;

                                        if (__exit(board, visited, word, 1, i, j))
                                                return true;

                                        visited[i][j] = false;
                                }
                        }
                }

                return false;
        }
};