Coding - Word Search

Problem Statement

Given an m x n grid of characters board and a string word, return true if the word exists in the grid, otherwise return false. The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

Examples

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

Constraints

• m and n are the number of rows and columns of the grid.
• 1 <= m * n <= 2 * 10^4
• 1 <= word.length() <= 10^3
• board[i][j] and word are composed of only lowercase and uppercase English letters.

Hints

• Consider using depth-first search (DFS) or breadth-first search (BFS) to explore the board for the word.
• When exploring a path, mark the visited cell to avoid revisiting it.
• After exploring all possible paths from a cell, unmark the cell to allow other paths to use it.