Word Search

Problem Overview
The "Word Search" problem involves determining if a given word exists in an m x n grid of characters, where the word must be formed by sequentially adjacent cells (horizontally or vertically neighboring). This is a classic backtracking problem tagged with Array, Matrix, and Backtracking, commonly asked in Microsoft interviews.[1][9]

Full Problem Statement

Given an m x n board of characters (a 2D array) and a string word, return true if the word exists in the board. 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 in a single word path.[9]

Input/Output Examples

Example 1

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Output: true
Explanation: One possible path is: A(0,0) → B(0,1) → C(0,2) → C(1,2) → E(1,3) → D(2,1).[1][9]

Example 2

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
Output: true
Explanation: One possible path is: S(1,0) → E(1,3) → E(2,3).[9][1]

Example 3

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
Output: false
Explanation: No valid path exists for "ABCB".[9]

Constraints

• m == board.length
• n = board[i].length
• 1 ≤ m, n ≤ 6
• 1 ≤ word.length ≤ 15
• board and word consist of only lowercase and uppercase English letters.
• Typically, the grid dimensions are small to make backtracking feasible.[1][9]