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.
One effective method to solve this problem is to use Depth-First Search (DFS) combined with backtracking. This approach involves starting from each cell and attempting to find the word by traversing adjacent cells, backtracking whenever a dead end is encountered.
DFS coupled with backtracking will be able to explore each possible path in the grid, returning true if a path spelling out the word is found, and false if all paths have been exhausted without success.
The function should mark a cell as visited before exploring further down its path and should unmark it (backtrack) when returning.
This solution uses a helper function, dfs(), to check character matches starting from each cell. The board cell is marked as visited by setting it to a null character. The function first checks boundary conditions and whether the target character matches the current cell before exploring in four directions (up, down, left, right). If the word is found, the function immediately returns true; otherwise, it backtracks.
C++
Java
Python
C#
JavaScript
Time Complexity: O(N * 3^L) where N is the number of cells and L is the length of the word. Each cell can have at most 3 valid directions to explore (excluding the direction we came from).
Space Complexity: O(L) due to recursion stack where L is the length of the word being searched.
An alternative but less optimal approach involves using Breadth-First Search (BFS). This approach can be useful for understanding the search pattern but is generally slower and less ideal compared to DFS for specific pathfinding problems.
Although BFS will attempt to explore each possibility layer-by-layer, it is less effective due to its nature of handling adjacency and backtracking in this specific kind of grid traversal problem. Still, it provides a clearer structure for paths explored and can be integrated with queue data structures for parallel processing.
The key difficulty with BFS in this problem is efficiently pruning unfruitful search branches early, which DFS inherently handles through natural backtracking.
This Python example uses a deque to handle BFS traversal. For each starting point matching the beginning of word, it attempts to queue possible paths that match subsequent characters. Although this implementation correctly attempts breadth-level searches, it lacks efficiency and effectiveness compared to DFS in terms of space and early pruning.
Time Complexity: Generally more than O(N * 3^L) as BFS does not effectively prune unpromising paths dynamically during search.
Space Complexity: O(N) because it may expand and hold large numbers of nodes in the worst case.
| Approach | Complexity |
|---|---|
| DFS with Backtracking | Time Complexity: O(N * 3^L) where N is the number of cells and L is the length of the word. Each cell can have at most 3 valid directions to explore (excluding the direction we came from). Space Complexity: O(L) due to recursion stack where L is the length of the word being searched. |
| BFS with Queue and Pruning | Time Complexity: Generally more than O(N * 3^L) as BFS does not effectively prune unpromising paths dynamically during search. Space Complexity: O(N) because it may expand and hold large numbers of nodes in the worst case. |
| 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 |
Word Search - Backtracking - Leetcode 79 - Python • NeetCode • 380,744 views views
Watch 9 more video solutions →Practice Word Search with our built-in code editor and test cases.
Practice on FleetCode