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 character grid and a target word, determine whether the word exists in the grid. You can move horizontally or vertically to adjacent cells, and each cell can be used only once in the current path. The challenge is efficiently exploring possible paths while preventing revisiting cells.
Approach 1: DFS with Backtracking (O(m * n * 4^L) time, O(L) space)
This approach treats the grid like a graph and performs a depth‑first search from every cell that matches the first character of the word. From each position, recursively explore up, down, left, and right while checking whether the next character matches the word. A temporary mark (such as replacing the character or using a visited set) prevents revisiting the same cell in the current path. If a path fails, restore the cell and backtrack to try another direction.
The key insight is that you only explore paths that match the word prefix. The branching factor is at most 4 directions, and recursion depth equals the word length L. This pruning keeps the search manageable even though the theoretical worst case is exponential. DFS with backtracking is the most common interview solution for problems involving path exploration in a matrix combined with constraint-based search from backtracking.
Approach 2: BFS with Queue and Pruning (O(m * n * 4^L) time, higher space)
This variation explores possible paths level by level using a queue. Each queue state stores the current cell, index in the word, and the set or mask of visited cells. Start BFS from every grid cell that matches the first character, then expand to neighbors that match the next character. States that violate constraints (character mismatch or revisiting a cell) are pruned immediately.
BFS guarantees that all prefixes of the word are explored systematically. However, the queue can grow large because multiple partial paths are stored simultaneously, increasing memory usage compared to DFS recursion. This approach is less common in interviews but useful when you want explicit control over state exploration or iterative traversal instead of recursion.
Both approaches rely heavily on efficient grid traversal and prefix matching. The board itself is typically represented as a 2D array, and the target pattern is a string that must be matched sequentially.
Recommended for interviews: DFS with backtracking is the expected solution. Interviewers look for correct recursion structure, proper visited handling, and early pruning when characters do not match. Starting DFS from each cell demonstrates full coverage of the grid, while backtracking shows you understand how to explore and undo state changes efficiently. BFS can work but usually consumes more memory and adds unnecessary complexity for this problem.
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.
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.
Python
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.
We can enumerate each position (i, j) in the grid as the starting point of the search, and then start a depth-first search from the starting point. If we can search to the end of the word, it means the word exists, otherwise, it means the word does not exist.
Therefore, we design a function dfs(i, j, k), which represents whether we can successfully search from the (i, j) position of the grid, starting from the kth character of the word. The execution steps of the function dfs(i, j, k) are as follows:
k = |word|-1, it means that we have searched to the last character of the word. At this time, we only need to judge whether the character at the (i, j) position of the grid is equal to word[k]. If they are equal, it means the word exists, otherwise, it means the word does not exist. Whether the word exists or not, there is no need to continue to search, so return the result directly.word[k] character is not equal to the character at the (i, j) position of the grid, it means that the search failed this time, so return false directly.(i, j) position of the grid in c, and then modify the character at this position to a special character '0', indicating that the character at this position has been used to prevent it from being reused in subsequent searches. Then we start from the up, down, left, and right directions of the (i, j) position to search for the k+1th character in the grid. If any direction is successful, it means the search is successful, otherwise, it means the search failed. At this time, we need to restore the character at the (i, j) position of the grid, that is, put c back to the (i, j) position (backtracking).In the main function, we enumerate each position (i, j) in the grid as the starting point. If calling dfs(i, j, 0) returns true, it means the word exists, otherwise, it means the word does not exist, so return false.
The time complexity is O(m times n times 3^k), and the space complexity is O(min(m times n, k)). Here, m and n are the number of rows and columns of the grid, respectively; and k is the length of the string word.
Python
Java
C++
Go
TypeScript
JavaScript
Rust
C#
| 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. |
| DFS (Backtracking) | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| DFS with Backtracking | O(m * n * 4^L) | O(L) | Best general solution for grid path problems and the expected interview approach |
| BFS with Queue and Pruning | O(m * n * 4^L) | O(m * n * 4^L) | Useful when implementing iterative traversal or exploring states level by level |
Word Search - Backtracking - Leetcode 79 - Python • NeetCode • 460,317 views views
Watch 9 more video solutions →Practice Word Search with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor