MediumBacktracking
Word Search
amazonmetamicrosoftbloomberggoogleappleoracle
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.
Examples
Example 1
Input
board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Output
true
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
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
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)
One problem, two ways to prep
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.