LeetCode 79 - Word Search

题目描述

[Medium]

Given an m x n grid of characters board and a string word, return true if word exists in the grid.

The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.

Example 1:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Output: true

Example 2:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
Output: true

Example 3:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
Output: false

思路

backtracking at each level, and we mark the cell as visited by setting it to ‘#’.

代码

class Solution {
public:

    bool dfs(vector<vector<char>>& board, string& word, int i, int j, int idx) {
        // Base case: all characters found
        if (idx == word.size()) return true;

        // Out of bounds or mismatch
        if (i < 0 || i >= board.size() || j < 0 || j >= board[0].size() || board[i][j] != word[idx])
            return false;

        // Mark the cell as visited
        char temp = board[i][j];
        board[i][j] = '#'; // mark as visited

        // Explore all 4 directions
        bool found = dfs(board, word, i + 1, j, idx + 1) ||
                     dfs(board, word, i - 1, j, idx + 1) ||
                     dfs(board, word, i, j + 1, idx + 1) ||
                     dfs(board, word, i, j - 1, idx + 1);

        // Backtrack: restore the character
        board[i][j] = temp;

        return found;
    }


    bool exist(vector<vector<char>>& board, string word) {
        int m = board.size();
        int n = board[0].size();

        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (dfs(board, word, i, j, 0)) 
                    return true;
            }
        }
        return false;
    }
};