Word Search
Return true if the word can be constructed from adjacent cells.
Examples
Input: [["ABCE","SFCS","ADEE"],"ABCCED"]
Output: true
Input: [["ABCE","SFCS","ADEE"],"SEE"]
Output: true
Hints
Use Depth-First Search (DFS) to explore all possible paths starting from each cell in the board.
Implement backtracking by temporarily marking visited cells (e.g., with a special character) and reverting the change after exploring all directions.
Optimize by pruning paths early if the current character doesn’t match the next character in the word or if the remaining word length exceeds the available cells in the board.
Related Problems
Word Search
Return true if the word can be constructed from adjacent cells.