Word Search
Given an m x n grid of characters board and a string word, return true if word exists in the grid.
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.
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 starting from the top-left 'A', going right to 'B', 'C', then down to 'C', 'E', and left to 'D'.
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 starting from board[1][3] = 'S', going down to 'E', then left to '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 formed because the 'B' at board[0][1] would need to be reused.
Examples
Example 1
Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Output: true
Explanation: The path A→B→C→C→E→D traces through adjacent cells without reusing any cell.
Example 2
Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
Output: true
Explanation: Starting from S at position (1,3), moving down to E at (2,3), then left to E at (2,2).
Example 3
Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
Output: false
Explanation: Cannot form ABCB because the B at (0,1) would need to be visited twice.
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
Optimal Complexity
Time
O(m * n * 4^L)
Space
O(L)
Choose between solo practice and interview simulation
Practice Mode keeps things simple with code + tests. AI Interview Mode adds voice, pressure, and a post-round score summary.