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?
The Word Search problem is commonly solved using a Depth-First Search (DFS) with backtracking. The grid can be treated as a matrix where we attempt to match the target word starting from every cell. If the first character matches, we recursively explore neighboring cells (up, down, left, right) to match the next character.
To avoid reusing the same cell within a single path, a temporary visited marking strategy is used. This can be done either with a separate visited matrix or by modifying the current cell temporarily and restoring it during backtracking. The recursion continues until either all characters of the word are matched or the path becomes invalid.
This approach ensures all valid paths are explored while pruning mismatches early. If the board has M × N cells and the word length is L, the search explores branching paths with controlled backtracking, making the algorithm efficient for typical interview constraints.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| DFS with Backtracking | O(M × N × 4^L) | O(L) recursion stack |
NeetCode
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.
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.
1#include <stdbool.h>
2#include <string.h>
3
4bool dfs(char** board, int boardSize, int* boardColSize
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.
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.
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.
1from collections import deque
2
3class Solution
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, Word Search is a common interview question in many top tech companies including FAANG. It tests understanding of backtracking, recursion, and grid traversal patterns.
The optimal approach uses Depth-First Search (DFS) with backtracking. Starting from each grid cell, the algorithm attempts to match characters of the target word while exploring adjacent cells and marking visited positions to avoid reuse.
A 2D matrix (grid) combined with recursion for DFS is the primary structure used. Some implementations also use a visited array or temporary cell modification to track visited positions during the search path.
Backtracking allows the algorithm to explore different paths while reverting changes when a path fails. This ensures each cell can be reused in different search paths without violating the rule of not revisiting the same cell within a single attempt.
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.