Approach Summary
DFS from every cell. Mark cell as visited by temporarily changing its value. Restore on backtrack.
Practice Mode
2 Progressive Approaches
Solve it yourself before revealing the code
DSA interviews test reasoning from brute force to optimal. Think through the constraints first.
Solution Progression (Brute Force → Most Optimized)
Understand the architectural evolution from naive baseline to optimal complexity.
| Approach | Time | Space | Core Strategy / Trade-off |
|---|---|---|---|
| 1 Approach 1: Backtracking with Visited Set | O(M * N * 4^L) | O(M * N) | Explores candidate paths using a visited hash set to maintain track of traversed cells during recursion. |
| 2 Approach 2: In-Place DFS Backtracking with Grid Mutation (Optimal) | O(M * N * 3^L) | O(L) | Temporarily modifies grid cell to a sentinel character `*` during traversal, restoring the original character on backtrack for O(L) space. |
Step 1: Baseline
Approach 1: Backtracking with Visited Set
Time: O(M * N * 4^L)
Space: O(M * N)
1. For every cell (r, c) on the grid: - If `board[r][c] == word[0]`, initiate DFS with `visited = set([(r, c)])`. - In `dfs(r, c, k)`: if `k == len(word) - 1`, return true. - For each neighbor `(nr, nc)`: if valid, not in `visited`, and `board[nr][nc] == word[k + 1]`, add to `visited` and recurse. - Remove `(nr, nc)` from `visited` when returning (backtrack). 2. Visited set operations add hashing overhead and memory allocation.
Approach 1: Backtracking with Visited Set Implementation
Approach 1: Backtracking with Visited Set
class Solution {
public boolean exist(char[][] board, String word) {
int m = board.length, n = board[0].length;
boolean[][] visited = new boolean[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (dfs(board, i, j, 0, word, visited)) return true;
}
}
return false;
}
boolean dfs(char[][] b, int r, int c, int idx, String w, boolean[][] vis) {
if (idx == w.length()) return true;
if (r < 0 || r >= b.length || c < 0 || c >= b[0].length || vis[r][c] || b[r][c] != w.charAt(idx)) return false;
vis[r][c] = true;
boolean found = dfs(b, r+1, c, idx+1, w, vis) || dfs(b, r-1, c, idx+1, w, vis) ||
dfs(b, r, c+1, idx+1, w, vis) || dfs(b, r, c-1, idx+1, w, vis);
vis[r][c] = false;
return found;
}
}class Solution {
public:
bool exist(vector<vector<char>>& board, string word) {
int m = board.size(), n = board[0].size();
vector<vector<bool>> vis(m, vector<bool>(n, false));
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (dfs(board, i, j, 0, word, vis)) return true;
}
}
return false;
}
bool dfs(vector<vector<char>>& b, int r, int c, int idx, string& w, vector<vector<bool>>& vis) {
if (idx == w.size()) return true;
if (r < 0 || r >= b.size() || c < 0 || c >= b[0].size() || vis[r][c] || b[r][c] != w[idx]) return false;
vis[r][c] = true;
bool found = dfs(b, r+1, c, idx+1, w, vis) || dfs(b, r-1, c, idx+1, w, vis) ||
dfs(b, r, c+1, idx+1, w, vis) || dfs(b, r, c-1, idx+1, w, vis);
vis[r][c] = false;
return found;
}
};class Solution:
def exist(self, board: list[list[str]], word: str) -> bool:
m, n = len(board), len(board[0])
def dfs(r, c, idx, visited):
if idx == len(word): return True
if r < 0 or r >= m or c < 0 or c >= n or (r, c) in visited or board[r][c] != word[idx]:
return False
visited.add((r, c))
for dr, dc in [(1,0), (-1,0), (0,1), (0,-1)]:
if dfs(r + dr, c + dc, idx + 1, visited):
return True
visited.remove((r, c))
return False
for i in range(m):
for j in range(n):
if dfs(i, j, 0, set()): return True
return Falsevar exist = function(board, word) {
const m = board.length, n = board[0].length;
const visited = new Set();
function dfs(r, c, idx) {
if (idx === word.length) return true;
const key = `${r},${c}`;
if (r < 0 || r >= m || c < 0 || c >= n || visited.has(key) || board[r][c] !== word[idx]) {
return false;
}
visited.add(key);
const res = dfs(r+1, c, idx+1) || dfs(r-1, c, idx+1) || dfs(r, c+1, idx+1) || dfs(r, c-1, idx+1);
visited.delete(key);
return res;
}
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (dfs(i, j, 0)) return true;
}
}
return false;
}; Step 2: Most Optimized
Approach 2: In-Place DFS Backtracking with Grid Mutation (Optimal)
Time: O(M * N * 3^L)
Space: O(L)
1. Loop over each cell `(i, j)`. If `board[i][j] == word[0]`, invoke `dfs(i, j, 0)`. 2. In `dfs(r, c, idx)`: - If `idx == word.length`, all letters matched, return true. - If out of bounds or `board[r][c] != word[idx]`, return false. - Save `temp = board[r][c]` and set `board[r][c] = '*'`. - Recurse in 4 directions for `idx + 1`. - Restore `board[r][c] = temp`. 3. Eliminates any visited data structure allocation; auxiliary space is purely the recursion call stack of depth at most `word.length`.
Approach 2: In-Place DFS Backtracking with Grid Mutation (Optimal) Implementation
Approach 2: In-Place DFS Backtracking with Grid Mutation (Optimal)
class Solution {
public boolean exist(char[][] board, String word) {
int m = board.length, n = board[0].length;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (board[i][j] == word.charAt(0) && dfs(board, i, j, 0, word)) return true;
}
}
return false;
}
boolean dfs(char[][] b, int r, int c, int idx, String w) {
if (idx == w.length()) return true;
if (r < 0 || r >= b.length || c < 0 || c >= b[0].length || b[r][c] != w.charAt(idx)) return false;
char temp = b[r][c];
b[r][c] = '*';
boolean found = dfs(b, r+1, c, idx+1, w) || dfs(b, r-1, c, idx+1, w) ||
dfs(b, r, c+1, idx+1, w) || dfs(b, r, c-1, idx+1, w);
b[r][c] = temp;
return found;
}
}class Solution {
public:
bool exist(vector<vector<char>>& board, string word) {
int m = board.size(), n = board[0].size();
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (board[i][j] == word[0] && dfs(board, i, j, 0, word)) return true;
}
}
return false;
}
bool dfs(vector<vector<char>>& b, int r, int c, int idx, string& w) {
if (idx == w.size()) return true;
if (r < 0 || r >= b.size() || c < 0 || c >= b[0].size() || b[r][c] != w[idx]) return false;
char temp = b[r][c];
b[r][c] = '*';
bool found = dfs(b, r+1, c, idx+1, w) || dfs(b, r-1, c, idx+1, w) ||
dfs(b, r, c+1, idx+1, w) || dfs(b, r, c-1, idx+1, w);
b[r][c] = temp;
return found;
}
};class Solution:
def exist(self, board: list[list[str]], word: str) -> bool:
m, n = len(board), len(board[0])
def dfs(r, c, idx):
if idx == len(word): return True
if r < 0 or r >= m or c < 0 or c >= n or board[r][c] != word[idx]:
return False
temp, board[r][c] = board[r][c], '*'
found = (dfs(r + 1, c, idx + 1) or dfs(r - 1, c, idx + 1) or
dfs(r, c + 1, idx + 1) or dfs(r, c - 1, idx + 1))
board[r][c] = temp
return found
for i in range(m):
for j in range(n):
if board[i][j] == word[0] and dfs(i, j, 0): return True
return Falsevar exist = function(board, word) {
const m = board.length, n = board[0].length;
function dfs(r, c, idx) {
if (idx === word.length) return true;
if (r < 0 || r >= m || c < 0 || c >= n || board[r][c] !== word[idx]) return false;
const temp = board[r][c];
board[r][c] = '*';
const found = dfs(r+1, c, idx+1) || dfs(r-1, c, idx+1) || dfs(r, c+1, idx+1) || dfs(r, c-1, idx+1);
board[r][c] = temp;
return found;
}
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (board[i][j] === word[0] && dfs(i, j, 0)) return true;
}
}
return false;
};Edge Cases to Watch
- Word length exceeds total grid cells (L > M * N) — return false immediately
- Single character word matching board[0][0] — returns true instantly on first step
- Word cannot be formed because character frequency on board is insufficient
- Self-intersecting paths — temporarily setting board[i][j] = '*' ensures a cell is never reused in the same word instance
Algorithmic Pattern
View Pattern Guide →
Master the Backtracking Pattern
Study the core invariant, step-by-step decision framework, and common interview traps for the Backtracking pattern.
Framework: Backtracking • Interview Prep: Tested at FAANG •
Explore all Backtracking problems & invariants →
How to Recognize This Pattern
- Find word path in grid
- Mark-and-restore visited cells
Complexity Analysis
Time Complexity
O(m × n × 4^L)
Space Complexity
O(L)
Tags
Array Matrix Backtracking DFS
Frequently Asked Questions
What is the optimal time and space complexity for Word Search?
The optimal solution for Word Search achieves O(m × n × 4^L) runtime complexity and requires O(L) auxiliary space. Time Complexity is O(M * N * 3^L) where M is the number of rows, N is the number of columns, and L is the length of the word. From each character, we explore 3 directions (excluding the direction we arrived from). In the worst case we explore up to 3^L paths per starting cell. Space Complexity is O(L) representing the recursion call stack depth, which never exceeds the length of the word.
How do I identify that Word Search requires the Backtracking pattern?
In technical interviews, look for key problem signals: Find word path in grid; Mark-and-restore visited cells. Recognizing these invariants allows you to bypass naive brute-force exhaustive search in favor of Backtracking strategy.
What critical edge cases must be handled in Word Search?
Essential edge cases to verify include: Word length exceeds total grid cells (L > M * N) — return false immediately; Single character word matching board[0][0] — returns true instantly on first step; Word cannot be formed because character frequency on board is insufficient; Self-intersecting paths — temporarily setting board[i][j] = '*' ensures a cell is never reused in the same word instance. Always walk through these scenarios with your interviewer before coding.
Which tech companies frequently ask Word Search?
Word Search is a Medium-difficulty question tagged with high recurrence. It is actively asked in technical screening and onsite interview loops at Amazon, Facebook, Microsoft, Bloomberg.