Top Interview 150 P79 Word Search

---

Timeline

Timeline

2025-11-30

init

---

Problem:

P79 Word Search

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

Backtracking: iterate over each starting point, and mark visited cells on the board to avoid revisiting.

#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++) { //Iterate over each starting point
				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 rewrite, classic backtracking approach.

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

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

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

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

                // Down
                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 and word consist only of uppercase and lowercase English letters.

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