Watch 10 video solutions for Word Search, a medium level problem involving Array, String, Backtracking. This walkthrough by NeetCode has 380,744 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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
Example 2:
Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE" Output: true
Example 3:
Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB" Output: false
Constraints:
m == board.lengthn = board[i].length1 <= m, n <= 61 <= word.length <= 15board and word consists of only lowercase and uppercase English letters.
Follow up: Could you use search pruning to make your solution faster with a larger board?
Problem Overview: Given an m x n grid of characters and a target word, determine if the word can be formed by sequentially adjacent cells. Adjacent means up, down, left, or right. Each cell can be used only once in a path.
Approach 1: DFS with Backtracking (O(m * n * 4^L) time, O(L) space)
The most common solution treats the grid as a search space and performs depth-first search from every cell that matches the first letter of the word. From each position, recursively explore the four directions while matching the next character. Mark the current cell as visited (often by temporarily modifying the board or using a visited set) so the path cannot reuse it. If the recursion reaches the final character, the word exists. Backtracking restores the cell after exploring a path so other paths can reuse it. In the worst case, each step branches to four directions for every character, giving O(m * n * 4^L) time where L is the word length, and O(L) recursion stack space.
This approach combines backtracking with grid traversal. It works well because the search depth is limited by the word length, not the board size. Early pruning occurs whenever a character mismatch happens.
Approach 2: BFS with Queue and Pruning (O(m * n * 4^L) time, higher auxiliary space)
A breadth-first variation explores candidate paths level by level using a queue. Each queue entry stores the current position, the index in the word, and the set of visited cells in that path. Start by pushing all grid cells that match the first character. For each state, expand to neighboring cells that match the next character and are not already used in the current path. Prune immediately when characters do not match or when the next move revisits a cell.
This approach models the search as expanding states across the grid, which can be easier to visualize when debugging. However, storing visited sets for many parallel paths increases memory usage. Because of that overhead, BFS is rarely preferred in interviews but can still work for moderate grid sizes.
The problem is fundamentally a path search in a matrix combined with character matching from a string. Efficient pruning and careful handling of visited cells determine performance.
Recommended for interviews: DFS with backtracking is the expected solution. It is concise, uses minimal extra memory, and demonstrates strong understanding of recursive search and state restoration. Interviewers typically look for correct boundary checks, proper visited handling, and early termination once the word is found.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| DFS with Backtracking | O(m * n * 4^L) | O(L) | General case and most interview settings where recursion and pruning efficiently explore paths |
| BFS with Queue and Pruning | O(m * n * 4^L) | O(m * n * L) | When modeling the search as expanding states or when iterative traversal is preferred over recursion |