Word Search

Problem Statement

Given an m x n 2D 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 a cell, and the same letter cell may not be used more than once.

Constraints

• m and n are the number of rows and columns in the grid.
• Each cell in the grid contains only lowercase English letters.
• word is composed of lowercase English letters.

Examples

Example 1:

Input:

• board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]]
• word = "ABCCED"

Output:

• true

Explanation:

• The word "ABCCED" can be found by following the path A -> B -> C -> C -> E -> D -> E.

Example 2:

Input:

• board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]]
• word = "SEE"

Output:

• true

Explanation:

• The word "SEE" can be found by following the path S -> E -> E.

Example 3:

Input:

• board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]]
• word = "ABCB"

Output:

• false

Explanation:

• The word "ABCB" cannot be found in the grid.

Example 4:

Input:

• board = []
• word = "ABCB"

Output:

• false

Explanation:

• The board is empty, so there is no way to find the word.

Hints

1. Use backtracking to explore all possible paths in the grid.
2. Use a set or a boolean array to track visited cells.
3. After exploring a path, backtrack by resetting the visited status of cells and trying a different path.