79. Word Search - Explanation

Description

Given a 2-D grid of characters board and a string word, return true if the word is present in the grid, otherwise return false.

For the word to be present it must be possible to form it with a path in the board with horizontally or vertically neighboring cells. The same cell may not be used more than once in a word.

Example 1:

Input: 
board = [
  ["A","B","C","D"],
  ["S","A","A","T"],
  ["A","C","A","E"]
],
word = "CAT"

Output: true

Example 2:

Input: 
board = [
  ["A","B","C","D"],
  ["S","A","A","T"],
  ["A","C","A","E"]
],
word = "BAT"

Output: false

Constraints:

1 <= board.length, board[i].length <= 5
1 <= word.length <= 10
board and word consists of only lowercase and uppercase English letters.

Topics

Recommended Time & Space Complexity

You should aim for a solution with O(m * (4^n)) time and O(n) space, where m is the number of cells in the given board and n is the size of the given word.

Hint 1

As we can start at any cell on the board, we can explore all paths from that cell. Can you think of an algorithm to do so? Also, you should consider a way to avoid visiting a cell that has already been visited in the current path.

Hint 2

We can use a hash set to avoid revisiting a cell in the current path by inserting the (row, col) of the visiting cell into the hash set and exploring all paths (four directions, as we can move to four neighboring cells) from that cell. Can you think of the base condition for this recursive path? Maybe you should consider the board boundaries, and also, we can extend a path if the character at the cell matches the character in the word.

Hint 3

We can use backtracking, starting from each cell on the board with coordinates (row, col) and index i for the given word. We return false if (row, col) is out of bounds or if board[row][col] != word[i]. When i reaches the end of the word, we return true, indicating a valid path. At each step, we add (row, col) to a hash set to avoid revisiting cells. After exploring the four possible directions, we backtrack and remove (row, col) from the hash set.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Backtracking - Exploring all possible paths by making choices, recursing, and undoing choices to try alternatives
Depth-First Search (DFS) - Traversing a graph or grid by exploring as far as possible along each branch before backtracking
2D Grid Traversal - Moving through a matrix in four directions while tracking visited cells to avoid revisiting
Recursion - Understanding recursive function calls and base cases for termination

1. Backtracking (Hash Set)

Intuition

We need to check if the word can be formed by walking up/down/left/right on the grid, using each cell at most once in the same path.

So for every cell, we try to start the word there:

If the current cell matches the current character, we move to its 4 neighbors for the next character.
While exploring, we mark the cell as visited (in a hash set) so we don't reuse it in the same path.
If a path fails, we undo (backtrack) the visit and try other directions.

If we ever match all characters, we return true (found the word).

Algorithm

For each cell in the grid, attempt to start matching word from that cell.
Use DFS with (row, col, i) where i is the index in word we need to match.
In DFS:
- If i == len(word), all characters matched → return true.
- If out of bounds, mismatch, or already visited → return false.
- Mark (row, col) as visited.
- Recurse to 4 neighbors with i + 1.
- Unmark (row, col) (backtrack).
If any start cell returns true, answer is true; otherwise false.

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        ROWS, COLS = len(board), len(board[0])
        path = set()

        def dfs(r, c, i):
            if i == len(word):
                return True

            if (min(r, c) < 0 or
                r >= ROWS or c >= COLS or
                word[i] != board[r][c] or
                (r, c) in path):
                return False

            path.add((r, c))
            res = (dfs(r + 1, c, i + 1) or
                   dfs(r - 1, c, i + 1) or
                   dfs(r, c + 1, i + 1) or
                   dfs(r, c - 1, i + 1))
            path.remove((r, c))
            return res

        for r in range(ROWS):
            for c in range(COLS):
                if dfs(r, c, 0):
                    return True
        return False

public class Solution {
    private int ROWS, COLS;
    private Set<Pair<Integer, Integer>> path = new HashSet<>();

    public boolean exist(char[][] board, String word) {
        ROWS = board.length;
        COLS = board[0].length;

        for (int r = 0; r < ROWS; r++) {
            for (int c = 0; c < COLS; c++) {
                if (dfs(board, word, r, c, 0)) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean dfs(char[][] board, String word, int r, int c, int i) {
        if (i == word.length()) {
            return true;
        }

        if (r < 0 || c < 0 || r >= ROWS || c >= COLS ||
            board[r][c] != word.charAt(i) ||
            path.contains(new Pair<>(r, c))) {
            return false;
        }

        path.add(new Pair<>(r, c));
        boolean res = dfs(board, word, r + 1, c, i + 1) ||
                      dfs(board, word, r - 1, c, i + 1) ||
                      dfs(board, word, r, c + 1, i + 1) ||
                      dfs(board, word, r, c - 1, i + 1);
        path.remove(new Pair<>(r, c));

        return res;
    }
}

class Solution {
public:
    int ROWS, COLS;
    set<pair<int, int>> path;

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

        for (int r = 0; r < ROWS; r++) {
            for (int c = 0; c < COLS; c++) {
                if (dfs(board, word, r, c, 0)) {
                    return true;
                }
            }
        }
        return false;
    }

    bool dfs(vector<vector<char>>& board, string word, int r, int c, int i) {
        if (i == word.length()) {
            return true;
        }

        if (r < 0 || c < 0 || r >= ROWS || c >= COLS ||
            board[r][c] != word[i] || path.count({r, c})) {
            return false;
        }

        path.insert({r, c});
        bool res = dfs(board, word, r + 1, c, i + 1) ||
                   dfs(board, word, r - 1, c, i + 1) ||
                   dfs(board, word, r, c + 1, i + 1) ||
                   dfs(board, word, r, c - 1, i + 1);
        path.erase({r, c});

        return res;
    }
};

class Solution {
    /**
     * @param {character[][]} board
     * @param {string} word
     * @return {boolean}
     */
    exist(board, word) {
        const ROWS = board.length;
        const COLS = board[0].length;
        const path = new Set();

        const dfs = (r, c, i) => {
            if (i === word.length) return true;
            if (
                r < 0 ||
                c < 0 ||
                r >= ROWS ||
                c >= COLS ||
                board[r][c] !== word[i] ||
                path.has(`${r},${c}`)
            ) {
                return false;
            }

            path.add(`${r},${c}`);
            const res =
                dfs(r + 1, c, i + 1) ||
                dfs(r - 1, c, i + 1) ||
                dfs(r, c + 1, i + 1) ||
                dfs(r, c - 1, i + 1);
            path.delete(`${r},${c}`);
            return res;
        };

        for (let r = 0; r < ROWS; r++) {
            for (let c = 0; c < COLS; c++) {
                if (dfs(r, c, 0)) return true;
            }
        }
        return false;
    }
}

public class Solution {
    private int ROWS, COLS;
    private HashSet<(int, int)> path = new HashSet<(int, int)>();

    public bool Exist(char[][] board, string word) {
        ROWS = board.Length;
        COLS = board[0].Length;

        for (int r = 0; r < ROWS; r++) {
            for (int c = 0; c < COLS; c++) {
                if (DFS(board, word, r, c, 0)) {
                    return true;
                }
            }
        }
        return false;
    }

    private bool DFS(char[][] board, string word, int r, int c, int i) {
        if (i == word.Length) {
            return true;
        }

        if (r < 0 || c < 0 || r >= ROWS || c >= COLS ||
            board[r][c] != word[i] || path.Contains((r, c))) {
            return false;
        }

        path.Add((r, c));
        bool res = DFS(board, word, r + 1, c, i + 1) ||
                   DFS(board, word, r - 1, c, i + 1) ||
                   DFS(board, word, r, c + 1, i + 1) ||
                   DFS(board, word, r, c - 1, i + 1);
        path.Remove((r, c));

        return res;
    }
}

class Solution {
    fun exist(board: Array<CharArray>, word: String): Boolean {
        val rows = board.size
        val cols = board[0].size
        val path = HashSet<Pair<Int, Int>>()

        fun dfs(r: Int, c: Int, i: Int): Boolean {
            if (i == word.length) return true
            if (r < 0 || c < 0 || r >= rows || c >= cols ||
                board[r][c] != word[i] || Pair(r, c) in path) {
                return false
            }

            path.add(Pair(r, c))
            val res = dfs(r + 1, c, i + 1) ||
                      dfs(r - 1, c, i + 1) ||
                      dfs(r, c + 1, i + 1) ||
                      dfs(r, c - 1, i + 1)
            path.remove(Pair(r, c))

            return res
        }

        for (r in 0 until rows) {
            for (c in 0 until cols) {
                if (dfs(r, c, 0)) {
                    return true
                }
            }
        }
        return false
    }
}

class Solution {
    func exist(_ board: [[Character]], _ word: String) -> Bool {
        let ROWS = board.count
        let COLS = board[0].count
        var path = Set<[Int]>()
        let wordArray = Array(word)

        func dfs(_ r: Int, _ c: Int, _ i: Int) -> Bool {
            if i == wordArray.count {
                return true
            }
            if (r < 0 || c < 0 || r >= ROWS || c >= COLS ||
                board[r][c] != wordArray[i] || path.contains([r, c])) {
                return false
            }

            path.insert([r, c])
            let res = dfs(r + 1, c, i + 1) ||
                      dfs(r - 1, c, i + 1) ||
                      dfs(r, c + 1, i + 1) ||
                      dfs(r, c - 1, i + 1)
            path.remove([r, c])
            return res
        }

        for r in 0..<ROWS {
            for c in 0..<COLS {
                if dfs(r, c, 0) {
                    return true
                }
            }
        }
        return false
    }
}

impl Solution {
    pub fn exist(board: Vec<Vec<char>>, word: String) -> bool {
        let rows = board.len();
        let cols = board[0].len();
        let word: Vec<char> = word.chars().collect();
        let mut path = HashSet::new();

        for r in 0..rows {
            for c in 0..cols {
                if Self::dfs(&board, &word, r as i32, c as i32, 0, &mut path) {
                    return true;
                }
            }
        }
        false
    }

    fn dfs(
        board: &Vec<Vec<char>>, word: &[char],
        r: i32, c: i32, i: usize,
        path: &mut HashSet<(i32, i32)>,
    ) -> bool {
        if i == word.len() { return true; }
        if r < 0 || c < 0 || r >= board.len() as i32
            || c >= board[0].len() as i32
            || board[r as usize][c as usize] != word[i]
            || path.contains(&(r, c))
        {
            return false;
        }

        path.insert((r, c));
        let res = Self::dfs(board, word, r + 1, c, i + 1, path)
            || Self::dfs(board, word, r - 1, c, i + 1, path)
            || Self::dfs(board, word, r, c + 1, i + 1, path)
            || Self::dfs(board, word, r, c - 1, i + 1, path);
        path.remove(&(r, c));
        res
    }
}

Time & Space Complexity

Time complexity: $O(m * 4 ^ n)$
Space complexity: $O(n)$

Where $m$ is the number of cells in the $board$ and $n$ is the length of the $word$ .

2. Backtracking (Visited Array)

Intuition

We try to form the word by walking through adjacent cells (up, down, left, right) in the grid.
Each cell can be used only once in the current path, so we keep a visited matrix to mark cells that are already part of the path.

From every cell, we attempt to match the word starting at index 0.
If at any point the character doesn't match, goes out of bounds, or the cell is already visited, we stop that path.
If all characters are matched successfully, the word exists in the grid and we return true.

Algorithm

Create a visited matrix of the same size as the board.
For every cell (r, c) in the grid, start a DFS to match the word from index 0.
In DFS (r, c, i):
- If i == len(word), all characters are matched → return true.
- If out of bounds, character mismatch, or already visited → return false.
- Mark the current cell as visited.
- Recurse to the 4 neighboring cells with i + 1.
- Unmark the cell (backtrack).
If any DFS call returns true, return true.
If all starts fail, return false.

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        ROWS, COLS = len(board), len(board[0])
        visited = [[False for _ in range(COLS)] for _ in range(ROWS)]

        def dfs(r, c, i):
            if i == len(word):
                return True
            if (r < 0 or c < 0 or r >= ROWS or c >= COLS or
                word[i] != board[r][c] or visited[r][c]):
                return False

            visited[r][c] = True
            res = (dfs(r + 1, c, i + 1) or
                   dfs(r - 1, c, i + 1) or
                   dfs(r, c + 1, i + 1) or
                   dfs(r, c - 1, i + 1))
            visited[r][c] = False
            return res

        for r in range(ROWS):
            for c in range(COLS):
                if dfs(r, c, 0):
                    return True
        return False

public class Solution {
    private int ROWS, COLS;
    private boolean[][] visited;

    public boolean exist(char[][] board, String word) {
        ROWS = board.length;
        COLS = board[0].length;
        visited = new boolean[ROWS][COLS];

        for (int r = 0; r < ROWS; r++) {
            for (int c = 0; c < COLS; c++) {
                if (dfs(board, word, r, c, 0)) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean dfs(char[][] board, String word, int r, int c, int i) {
        if (i == word.length()) {
            return true;
        }

        if (r < 0 || c < 0 || r >= ROWS || c >= COLS ||
            board[r][c] != word.charAt(i) || visited[r][c]) {
            return false;
        }

        visited[r][c] = true;
        boolean res = dfs(board, word, r + 1, c, i + 1) ||
                      dfs(board, word, r - 1, c, i + 1) ||
                      dfs(board, word, r, c + 1, i + 1) ||
                      dfs(board, word, r, c - 1, i + 1);
        visited[r][c] = false;

        return res;
    }
}

class Solution {
public:
    int ROWS, COLS;
    vector<vector<bool>> visited;

    bool exist(vector<vector<char>>& board, string word) {
        ROWS = board.size();
        COLS = board[0].size();
        visited = vector<vector<bool>>(ROWS, vector<bool>(COLS, false));

        for (int r = 0; r < ROWS; r++) {
            for (int c = 0; c < COLS; c++) {
                if (dfs(board, word, r, c, 0)) {
                    return true;
                }
            }
        }
        return false;
    }

    bool dfs(vector<vector<char>>& board, string word, int r, int c, int i) {
        if (i == word.length()) {
            return true;
        }

        if (r < 0 || c < 0 || r >= ROWS || c >= COLS ||
            board[r][c] != word[i] || visited[r][c]) {
            return false;
        }

        visited[r][c] = true;
        bool res = dfs(board, word, r + 1, c, i + 1) ||
                   dfs(board, word, r - 1, c, i + 1) ||
                   dfs(board, word, r, c + 1, i + 1) ||
                   dfs(board, word, r, c - 1, i + 1);
        visited[r][c] = false;

        return res;
    }
};

class Solution {
    /**
     * @param {character[][]} board
     * @param {string} word
     * @return {boolean}
     */
    exist(board, word) {
        const ROWS = board.length;
        const COLS = board[0].length;
        const visited = Array.from({ length: ROWS }, () =>
            Array(COLS).fill(false),
        );

        const dfs = (r, c, i) => {
            if (i === word.length) return true;
            if (
                r < 0 ||
                c < 0 ||
                r >= ROWS ||
                c >= COLS ||
                board[r][c] !== word[i] ||
                visited[r][c]
            ) {
                return false;
            }

            visited[r][c] = true;
            const res =
                dfs(r + 1, c, i + 1) ||
                dfs(r - 1, c, i + 1) ||
                dfs(r, c + 1, i + 1) ||
                dfs(r, c - 1, i + 1);
            visited[r][c] = false;
            return res;
        };

        for (let r = 0; r < ROWS; r++) {
            for (let c = 0; c < COLS; c++) {
                if (dfs(r, c, 0)) return true;
            }
        }
        return false;
    }
}

public class Solution {
    private int ROWS, COLS;
    private bool[,] visited;

    public bool Exist(char[][] board, string word) {
        ROWS = board.Length;
        COLS = board[0].Length;
        visited = new bool[ROWS, COLS];

        for (int r = 0; r < ROWS; r++) {
            for (int c = 0; c < COLS; c++) {
                if (DFS(board, word, r, c, 0)) {
                    return true;
                }
            }
        }
        return false;
    }

    private bool DFS(char[][] board, string word, int r, int c, int i) {
        if (i == word.Length) {
            return true;
        }

        if (r < 0 || c < 0 || r >= ROWS || c >= COLS ||
            board[r][c] != word[i] || visited[r, c]) {
            return false;
        }

        visited[r, c] = true;
        bool res = DFS(board, word, r + 1, c, i + 1) ||
                   DFS(board, word, r - 1, c, i + 1) ||
                   DFS(board, word, r, c + 1, i + 1) ||
                   DFS(board, word, r, c - 1, i + 1);
        visited[r, c] = false;

        return res;
    }
}

func exist(board [][]byte, word string) bool {
    rows, cols := len(board), len(board[0])
    visited := make([][]bool, rows)
    for i := range visited {
        visited[i] = make([]bool, cols)
    }

    var dfs func(r, c, i int) bool
    dfs = func(r, c, i int) bool {
        if i == len(word) {
            return true
        }
        if r < 0 || c < 0 || r >= rows || c >= cols ||
           board[r][c] != word[i] || visited[r][c] {
            return false
        }

        visited[r][c] = true
        res := dfs(r+1, c, i+1) ||
               dfs(r-1, c, i+1) ||
               dfs(r, c+1, i+1) ||
               dfs(r, c-1, i+1)
        visited[r][c] = false

        return res
    }

    for r := 0; r < rows; r++ {
        for c := 0; c < cols; c++ {
            if dfs(r, c, 0) {
                return true
            }
        }
    }
    return false
}

class Solution {
    fun exist(board: Array<CharArray>, word: String): Boolean {
        val rows = board.size
        val cols = board[0].size
        val visited = Array(rows) { BooleanArray(cols) }

        fun dfs(r: Int, c: Int, i: Int): Boolean {
            if (i == word.length) return true
            if (r < 0 || c < 0 || r >= rows || c >= cols ||
                board[r][c] != word[i] || visited[r][c]) {
                return false
            }

            visited[r][c] = true
            val res = dfs(r + 1, c, i + 1) ||
                      dfs(r - 1, c, i + 1) ||
                      dfs(r, c + 1, i + 1) ||
                      dfs(r, c - 1, i + 1)
            visited[r][c] = false

            return res
        }

        for (r in 0 until rows) {
            for (c in 0 until cols) {
                if (dfs(r, c, 0)) {
                    return true
                }
            }
        }
        return false
    }
}

class Solution {
    func exist(_ board: [[Character]], _ word: String) -> Bool {
        let ROWS = board.count
        let COLS = board[0].count
        var visited = Array(repeating: Array(repeating: false, count: COLS), count: ROWS)
        let wordArray = Array(word)

        func dfs(_ r: Int, _ c: Int, _ i: Int) -> Bool {
            if i == wordArray.count {
                return true
            }
            if (r < 0 || c < 0 || r >= ROWS || c >= COLS ||
                board[r][c] != wordArray[i] || visited[r][c]) {
                return false
            }

            visited[r][c] = true
            let res = dfs(r + 1, c, i + 1) ||
                      dfs(r - 1, c, i + 1) ||
                      dfs(r, c + 1, i + 1) ||
                      dfs(r, c - 1, i + 1)
            visited[r][c] = false
            return res
        }

        for r in 0..<ROWS {
            for c in 0..<COLS {
                if dfs(r, c, 0) {
                    return true
                }
            }
        }
        return false
    }
}

impl Solution {
    pub fn exist(board: Vec<Vec<char>>, word: String) -> bool {
        let rows = board.len();
        let cols = board[0].len();
        let word: Vec<char> = word.chars().collect();
        let mut visited = vec![vec![false; cols]; rows];

        for r in 0..rows {
            for c in 0..cols {
                if Self::dfs(&board, &word, r as i32, c as i32, 0, &mut visited) {
                    return true;
                }
            }
        }
        false
    }

    fn dfs(
        board: &Vec<Vec<char>>, word: &[char],
        r: i32, c: i32, i: usize,
        visited: &mut Vec<Vec<bool>>,
    ) -> bool {
        if i == word.len() { return true; }
        if r < 0 || c < 0 || r >= board.len() as i32
            || c >= board[0].len() as i32
        {
            return false;
        }
        let (ru, cu) = (r as usize, c as usize);
        if board[ru][cu] != word[i] || visited[ru][cu] {
            return false;
        }

        visited[ru][cu] = true;
        let res = Self::dfs(board, word, r + 1, c, i + 1, visited)
            || Self::dfs(board, word, r - 1, c, i + 1, visited)
            || Self::dfs(board, word, r, c + 1, i + 1, visited)
            || Self::dfs(board, word, r, c - 1, i + 1, visited);
        visited[ru][cu] = false;
        res
    }
}

Time & Space Complexity

Time complexity: $O(m * 4 ^ n)$
Space complexity: $O(n)$

Where $m$ is the number of cells in the $board$ and $n$ is the length of the $word$ .

3. Backtracking (Optimal)

Intuition

We want to check if the word can be formed by moving up/down/left/right in the grid, using each cell at most once in a single path.

Instead of keeping a separate visited matrix (extra space), we temporarily mark the current cell as used by replacing its character with a special value (like '#').
This means:

If we ever see '#', we know this cell is already in our current path → we can't reuse it.
After exploring from that cell, we restore the original character (this is the "backtrack" step), so other paths can use it.

So the idea is:

Try every cell as a starting point.
Do DFS to match the word character by character.
Mark → explore neighbors → unmark.

Algorithm

Let ROWS, COLS be grid size.
Define dfs(r, c, i) meaning: "Can we match word[i...] starting from cell (r, c)?"
Base case: if i == len(word), we matched all characters → return true.
Fail cases: if out of bounds, current cell doesn't match word[i], or cell is already used ('#') → return false.
Mark the cell as used (set it to '#').
Try DFS in 4 directions with i + 1.
Restore the cell back to its original character (backtrack).
Run dfs(r, c, 0) from every cell (r, c). If any returns true, answer is true; otherwise false.

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

        def dfs(r, c, i):
            if i == len(word):
                return True
            if (r < 0 or c < 0 or r >= ROWS or c >= COLS or
                word[i] != board[r][c] or board[r][c] == '#'):
                return False

            board[r][c] = '#'
            res = (dfs(r + 1, c, i + 1) or
                   dfs(r - 1, c, i + 1) or
                   dfs(r, c + 1, i + 1) or
                   dfs(r, c - 1, i + 1))
            board[r][c] = word[i]
            return res

        for r in range(ROWS):
            for c in range(COLS):
                if dfs(r, c, 0):
                    return True
        return False

public class Solution {
    private int ROWS, COLS;

    public boolean exist(char[][] board, String word) {
        ROWS = board.length;
        COLS = board[0].length;

        for (int r = 0; r < ROWS; r++) {
            for (int c = 0; c < COLS; c++) {
                if (dfs(board, word, r, c, 0)) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean dfs(char[][] board, String word, int r, int c, int i) {
        if (i == word.length()) {
            return true;
        }
        if (r < 0 || c < 0 || r >= ROWS || c >= COLS ||
            board[r][c] != word.charAt(i) || board[r][c] == '#') {
            return false;
        }

        board[r][c] = '#';
        boolean res = dfs(board, word, r + 1, c, i + 1) ||
                      dfs(board, word, r - 1, c, i + 1) ||
                      dfs(board, word, r, c + 1, i + 1) ||
                      dfs(board, word, r, c - 1, i + 1);
        board[r][c] = word.charAt(i);
        return res;
    }
}

class Solution {
public:
    int ROWS, COLS;

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

        for (int r = 0; r < ROWS; r++) {
            for (int c = 0; c < COLS; c++) {
                if (dfs(board, word, r, c, 0)) {
                    return true;
                }
            }
        }
        return false;
    }

    bool dfs(vector<vector<char>>& board, string word, int r, int c, int i) {
        if (i == word.size()) {
            return true;
        }
        if (r < 0 || c < 0 || r >= ROWS || c >= COLS ||
            board[r][c] != word[i] || board[r][c] == '#') {
            return false;
        }

        board[r][c] = '#';
        bool res = dfs(board, word, r + 1, c, i + 1) ||
                   dfs(board, word, r - 1, c, i + 1) ||
                   dfs(board, word, r, c + 1, i + 1) ||
                   dfs(board, word, r, c - 1, i + 1);
        board[r][c] = word[i];
        return res;
    }
};

class Solution {
    /**
     * @param {character[][]} board
     * @param {string} word
     * @return {boolean}
     */
    exist(board, word) {
        const ROWS = board.length;
        const COLS = board[0].length;

        const dfs = (r, c, i) => {
            if (i === word.length) return true;
            if (
                r < 0 ||
                c < 0 ||
                r >= ROWS ||
                c >= COLS ||
                board[r][c] !== word[i] ||
                board[r][c] === '#'
            ) {
                return false;
            }

            board[r][c] = '#';
            const res =
                dfs(r + 1, c, i + 1) ||
                dfs(r - 1, c, i + 1) ||
                dfs(r, c + 1, i + 1) ||
                dfs(r, c - 1, i + 1);
            board[r][c] = word[i];
            return res;
        };

        for (let r = 0; r < ROWS; r++) {
            for (let c = 0; c < COLS; c++) {
                if (dfs(r, c, 0)) return true;
            }
        }
        return false;
    }
}

public class Solution {
    private int ROWS, COLS;

    public bool Exist(char[][] board, string word) {
        ROWS = board.Length;
        COLS = board[0].Length;

        for (int r = 0; r < ROWS; r++) {
            for (int c = 0; c < COLS; c++) {
                if (Dfs(board, word, r, c, 0)) {
                    return true;
                }
            }
        }
        return false;
    }

    private bool Dfs(char[][] board, string word, int r, int c, int i) {
        if (i == word.Length) {
            return true;
        }
        if (r < 0 || c < 0 || r >= ROWS || c >= COLS ||
        board[r][c] != word[i] || board[r][c] == '#') {
            return false;
        }

        board[r][c] = '#';
        bool res = Dfs(board, word, r + 1, c, i + 1) ||
                   Dfs(board, word, r - 1, c, i + 1) ||
                   Dfs(board, word, r, c + 1, i + 1) ||
                   Dfs(board, word, r, c - 1, i + 1);
        board[r][c] = word[i];
        return res;
    }
}

func exist(board [][]byte, word string) bool {
    rows, cols := len(board), len(board[0])

    var dfs func(r, c, i int) bool
    dfs = func(r, c, i int) bool {
        if i == len(word) {
            return true
        }
        if r < 0 || c < 0 || r >= rows || c >= cols ||
           board[r][c] != word[i] || board[r][c] == '#' {
            return false
        }

        temp := board[r][c]
        board[r][c] = '#'
        res := dfs(r+1, c, i+1) ||
               dfs(r-1, c, i+1) ||
               dfs(r, c+1, i+1) ||
               dfs(r, c-1, i+1)
        board[r][c] = temp

        return res
    }

    for r := 0; r < rows; r++ {
        for c := 0; c < cols; c++ {
            if dfs(r, c, 0) {
                return true
            }
        }
    }
    return false
}

class Solution {
    fun exist(board: Array<CharArray>, word: String): Boolean {
        val rows = board.size
        val cols = board[0].size

        fun dfs(r: Int, c: Int, i: Int): Boolean {
            if (i == word.length) return true
            if (r < 0 || c < 0 || r >= rows || c >= cols ||
                board[r][c] != word[i] || board[r][c] == '#') {
                return false
            }

            val temp = board[r][c]
            board[r][c] = '#'
            val res = dfs(r + 1, c, i + 1) ||
                      dfs(r - 1, c, i + 1) ||
                      dfs(r, c + 1, i + 1) ||
                      dfs(r, c - 1, i + 1)
            board[r][c] = temp

            return res
        }

        for (r in 0 until rows) {
            for (c in 0 until cols) {
                if (dfs(r, c, 0)) {
                    return true
                }
            }
        }
        return false
    }
}

class Solution {
    func exist(_ board: [[Character]], _ word: String) -> Bool {
        let ROWS = board.count
        let COLS = board[0].count
        let wordArray = Array(word)
        var board = board

        func dfs(_ r: Int, _ c: Int, _ i: Int) -> Bool {
            if i == wordArray.count {
                return true
            }
            if (r < 0 || c < 0 || r >= ROWS || c >= COLS ||
                board[r][c] != wordArray[i] || board[r][c] == "#") {
                return false
            }

            let temp = board[r][c]
            board[r][c] = "#"
            let res = dfs(r + 1, c, i + 1) ||
                      dfs(r - 1, c, i + 1) ||
                      dfs(r, c + 1, i + 1) ||
                      dfs(r, c - 1, i + 1)
            board[r][c] = temp
            return res
        }

        for r in 0..<ROWS {
            for c in 0..<COLS {
                if dfs(r, c, 0) {
                    return true
                }
            }
        }
        return false
    }
}

impl Solution {
    pub fn exist(mut board: Vec<Vec<char>>, word: String) -> bool {
        let rows = board.len();
        let cols = board[0].len();
        let word: Vec<char> = word.chars().collect();

        for r in 0..rows {
            for c in 0..cols {
                if Self::dfs(&mut board, &word, r as i32, c as i32, 0) {
                    return true;
                }
            }
        }
        false
    }

    fn dfs(
        board: &mut Vec<Vec<char>>, word: &[char],
        r: i32, c: i32, i: usize,
    ) -> bool {
        if i == word.len() { return true; }
        if r < 0 || c < 0 || r >= board.len() as i32
            || c >= board[0].len() as i32
        {
            return false;
        }
        let (ru, cu) = (r as usize, c as usize);
        if board[ru][cu] != word[i] || board[ru][cu] == '#' {
            return false;
        }

        board[ru][cu] = '#';
        let res = Self::dfs(board, word, r + 1, c, i + 1)
            || Self::dfs(board, word, r - 1, c, i + 1)
            || Self::dfs(board, word, r, c + 1, i + 1)
            || Self::dfs(board, word, r, c - 1, i + 1);
        board[ru][cu] = word[i];
        res
    }
}

Time & Space Complexity

Time complexity: $O(m * 4 ^ n)$
Space complexity: $O(n)$

Where $m$ is the number of cells in the $board$ and $n$ is the length of the $word$ .

Common Pitfalls

Not Restoring the Cell After Backtracking

When marking a cell as visited by changing its value (e.g., to '#'), forgetting to restore the original character after exploring all neighbors will permanently modify the board. This causes other paths starting from different cells to incorrectly treat valid cells as already visited.

Checking Visited Before Matching Character

Placing the visited check before the character match check can cause subtle bugs. If a cell is marked visited with a special character like '#', comparing board[r][c] != word[i] will correctly fail. However, if using a separate visited structure, the order of checks matters for correctness and clarity.

Forgetting to Match the First Character Before DFS

Starting DFS from every cell without first checking if board[r][c] == word[0] wastes time exploring paths that cannot possibly match the word. While not incorrect, this optimization significantly improves performance on large boards.