270. Word Search
🔗 LeetCode Problem: 79. Word Search
📊 Difficulty: Medium
🏷️ Topics: Array, Backtracking, Matrix
Problem Statement
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.length
- n = board[i].length
- 1 <= m, n <= 6
- 1 <= word.length <= 15
- board and word consists of only lowercase and uppercase English letters.
🌟 ELI5: The Simple Idea!
Think of it like finding a path through a maze:
You have a grid of letters:
A B C E
S F C S
A D E E
You need to spell: "ABCCED"
Start anywhere that has 'A':
Position (0,0): A ✓
From A, look for 'B' in 4 directions (up, down, left, right):
Right → (0,1): B ✓
From B, look for 'C':
Right → (0,2): C ✓
From C, look for 'C':
Down → (1,2): C ✓
From C, look for 'E':
Down → (2,2): E ✓
From E, look for 'D':
Left → (2,1): D ✓
Found "ABCCED"! ✓
Key Rules:
1. Can move: Up, Down, Left, Right (4 directions)
2. Can't move: Diagonally
3. Can't reuse: Same cell twice in one path
4. Must match: Letters in exact order
🎨 Visual Understanding
The Board and Word
Board:
Col: 0 1 2 3
Row 0: [A][B][C][E]
Row 1: [S][F][C][S]
Row 2: [A][D][E][E]
Word: "ABCCED"
↑ ↑ ↑ ↑ ↑ ↑
0 1 2 3 4 5 (indices)
The 4 Directions
From any cell (row, col), can move to:
↑ UP (row-1, col)
|
LEFT ← [X] → RIGHT (row, col+1)
(col-1) |
↓ DOWN (row+1, col)
Example from (1,1):
UP: (0,1)
DOWN: (2,1)
LEFT: (1,0)
RIGHT: (1,2)
Search Pattern
Start: Find all cells with first letter 'A'
Board:
[A] B C E ← (0,0) has 'A' → Try this!
S F C S
[A] D E E ← (2,0) has 'A' → Try this if first fails!
For each starting 'A':
Try to build word using DFS + Backtracking
Mark visited cells to avoid reuse
Unmark when backtracking
🎨 How Tracking Works - Visual Step by Step
Complete State Tracking for word="ABCCED"
Board:
0 1 2 3
0 [A] [B] [C] [E]
1 [S] [F] [C] [S]
2 [A] [D] [E] [E]
Word: "ABCCED" (need to find indices 0→5)
═══════════════════════════════════════════════════════════════
STEP 1: Find starting cell (matching word[0] = 'A')
═══════════════════════════════════════════════════════════════
Try cell (0,0):
Board State:
0 1 2 3
0 [A] [B] [C] [E] Current: (0,0) = 'A'
1 [S] [F] [C] [S] Word index: 0
2 [A] [D] [E] [E] Matching: 'A' == 'A' ✓
Visited:
0 1 2 3
0 [✓] [ ] [ ] [ ] ← Mark (0,0) as visited
1 [ ] [ ] [ ] [ ]
2 [ ] [ ] [ ] [ ]
Match word[0]='A' ✓ → Continue to word[1]='B'
═══════════════════════════════════════════════════════════════
STEP 2: From (0,0), look for word[1]='B' in 4 directions
═══════════════════════════════════════════════════════════════
Current position: (0,0)
Looking for: 'B'
Check 4 directions:
┌─────────────────────────────────────────┐
│ UP: (row-1, col) = (-1, 0) → Out of bounds ✗ │
│ DOWN: (row+1, col) = (1, 0) = 'S' ≠ 'B' ✗ │
│ LEFT: (row, col-1) = (0, -1) → Out of bounds ✗ │
│ RIGHT: (row, col+1) = (0, 1) = 'B' ✓ │
└─────────────────────────────────────────┘
Move RIGHT to (0,1):
Board State:
0 1 2 3
0 [A] {B} [C] [E] Current: (0,1) = 'B'
1 [S] [F] [C] [S] Word index: 1
2 [A] [D] [E] [E] Matching: 'B' == 'B' ✓
Visited:
0 1 2 3
0 [✓] [✓] [ ] [ ] ← Mark (0,1) as visited
1 [ ] [ ] [ ] [ ]
2 [ ] [ ] [ ] [ ]
Path so far: A → B
Match word[1]='B' ✓ → Continue to word[2]='C'
═══════════════════════════════════════════════════════════════
STEP 3: From (0,1), look for word[2]='C' in 4 directions
═══════════════════════════════════════════════════════════════
Current position: (0,1)
Looking for: 'C'
Check 4 directions:
┌─────────────────────────────────────────┐
│ UP: (-1, 1) → Out of bounds ✗ │
│ DOWN: (1, 1) = 'F' ≠ 'C' ✗ │
│ LEFT: (0, 0) = 'A' → Visited ✗ │
│ RIGHT: (0, 2) = 'C' ✓ │
└─────────────────────────────────────────┘
Move RIGHT to (0,2):
Board State:
0 1 2 3
0 [A] [B] {C} [E] Current: (0,2) = 'C'
1 [S] [F] [C] [S] Word index: 2
2 [A] [D] [E] [E] Matching: 'C' == 'C' ✓
Visited:
0 1 2 3
0 [✓] [✓] [✓] [ ] ← Mark (0,2) as visited
1 [ ] [ ] [ ] [ ]
2 [ ] [ ] [ ] [ ]
Path so far: A → B → C
Match word[2]='C' ✓ → Continue to word[3]='C'
═══════════════════════════════════════════════════════════════
STEP 4: From (0,2), look for word[3]='C' in 4 directions
═══════════════════════════════════════════════════════════════
Current position: (0,2)
Looking for: 'C' (second C in word!)
Check 4 directions:
┌─────────────────────────────────────────┐
│ UP: (-1, 2) → Out of bounds ✗ │
│ DOWN: (1, 2) = 'C' ✓ │
│ LEFT: (0, 1) = 'B' → Visited ✗ │
│ RIGHT: (0, 3) = 'E' ≠ 'C' ✗ │
└─────────────────────────────────────────┘
Move DOWN to (1,2):
Board State:
0 1 2 3
0 [A] [B] [C] [E] Current: (1,2) = 'C'
1 [S] [F] {C} [S] Word index: 3
2 [A] [D] [E] [E] Matching: 'C' == 'C' ✓
Visited:
0 1 2 3
0 [✓] [✓] [✓] [ ] ← Mark (1,2) as visited
1 [ ] [ ] [✓] [ ]
2 [ ] [ ] [ ] [ ]
Path so far: A → B → C → C
Match word[3]='C' ✓ → Continue to word[4]='E'
═══════════════════════════════════════════════════════════════
STEP 5: From (1,2), look for word[4]='E' in 4 directions
═══════════════════════════════════════════════════════════════
Current position: (1,2)
Looking for: 'E'
Check 4 directions:
┌─────────────────────────────────────────┐
│ UP: (0, 2) = 'C' → Visited ✗ │
│ DOWN: (2, 2) = 'E' ✓ │
│ LEFT: (1, 1) = 'F' ≠ 'E' ✗ │
│ RIGHT: (1, 3) = 'S' ≠ 'E' ✗ │
└─────────────────────────────────────────┘
Move DOWN to (2,2):
Board State:
0 1 2 3
0 [A] [B] [C] [E] Current: (2,2) = 'E'
1 [S] [F] [C] [S] Word index: 4
2 [A] [D] {E} [E] Matching: 'E' == 'E' ✓
Visited:
0 1 2 3
0 [✓] [✓] [✓] [ ] ← Mark (2,2) as visited
1 [ ] [ ] [✓] [ ]
2 [ ] [ ] [✓] [ ]
Path so far: A → B → C → C → E
Match word[4]='E' ✓ → Continue to word[5]='D'
═══════════════════════════════════════════════════════════════
STEP 6: From (2,2), look for word[5]='D' in 4 directions
═══════════════════════════════════════════════════════════════
Current position: (2,2)
Looking for: 'D' (last letter!)
Check 4 directions:
┌─────────────────────────────────────────┐
│ UP: (1, 2) = 'C' → Visited ✗ │
│ DOWN: (3, 2) → Out of bounds ✗ │
│ LEFT: (2, 1) = 'D' ✓ │
│ RIGHT: (2, 3) = 'E' ≠ 'D' ✗ │
└─────────────────────────────────────────┘
Move LEFT to (2,1):
Board State:
0 1 2 3
0 [A] [B] [C] [E] Current: (2,1) = 'D'
1 [S] [F] [C] [S] Word index: 5
2 [A] {D} [E] [E] Matching: 'D' == 'D' ✓
Visited:
0 1 2 3
0 [✓] [✓] [✓] [ ] ← Mark (2,1) as visited
1 [ ] [ ] [✓] [ ]
2 [ ] [✓] [✓] [ ]
Path so far: A → B → C → C → E → D
Match word[5]='D' ✓
═══════════════════════════════════════════════════════════════
STEP 7: Check if complete word found
═══════════════════════════════════════════════════════════════
Word index: 5 + 1 = 6
Word length: 6
6 == 6 → Complete word found! ✓
Final Path Visualization:
0 1 2 3
0 [A]→[B]→[C] [E]
↓
1 [S] [F] [C] [S]
↓
2 [A] [D]←[E] [E]
Path taken: (0,0)→(0,1)→(0,2)→(1,2)→(2,2)→(2,1)
Letters: A → B → C → C → E → D
Word: "ABCCED" ✓
FOUND! Return true
═══════════════════════════════════════════════════════════════
Example of Backtracking (Failed Path)
Let's say we tried a different path that FAILS:
═══════════════════════════════════════════════════════════════
Failed Path Example: word="ABCB"
═══════════════════════════════════════════════════════════════
Start: (0,0) = 'A' ✓
Move to: (0,1) = 'B' ✓
Move to: (0,2) = 'C' ✓
Board State:
0 1 2 3
0 [A] [B] {C} [E] Current: (0,2)
1 [S] [F] [C] [S] Looking for: 'B' (word[3])
2 [A] [D] [E] [E]
Visited:
0 1 2 3
0 [✓] [✓] [✓] [ ]
1 [ ] [ ] [ ] [ ]
2 [ ] [ ] [ ] [ ]
Check 4 directions from (0,2):
UP: Out of bounds ✗
DOWN: (1,2) = 'C' ≠ 'B' ✗
LEFT: (0,1) = 'B' but VISITED ✗
RIGHT: (0,3) = 'E' ≠ 'B' ✗
No valid move! BACKTRACK ⬅
Backtrack to (0,1):
Unmark (0,2): visited[0][2] = false
Board State:
0 1 2 3
0 [A] {B} [C] [E] Back to: (0,1)
1 [S] [F] [C] [S]
2 [A] [D] [E] [E]
Visited after backtracking:
0 1 2 3
0 [✓] [✓] [ ] [ ] ← (0,2) unmarked!
1 [ ] [ ] [ ] [ ]
2 [ ] [ ] [ ] [ ]
Try other directions from (0,1)...
All fail → Backtrack further
Eventually return false
═══════════════════════════════════════════════════════════════
🎯 Approach 1: Backtracking with Visited Array ⭐⭐
The Most Common Solution
Algorithm:
1. For each cell in board:
If cell == word[0]:
Try DFS from this cell
2. DFS(row, col, index):
- If index == word.length: Found complete word! ✓
- Mark current cell as visited
- Try 4 directions (up, down, left, right)
- If any direction leads to solution: return true
- Unmark cell (backtrack)
- Return false
Implementation
/**
* Backtracking with visited array
* Time: O(m × n × 4^L) where L = word length
* Space: O(L) - Recursion depth
*/
class Solution {
private int[][] directions = {{-1,0}, {1,0}, {0,-1}, {0,1}}; // up, down, left, right
public boolean exist(char[][] board, String word) {
int m = board.length;
int n = board[0].length;
boolean[][] visited = new boolean[m][n];
// Try starting from each cell
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (board[i][j] == word.charAt(0)) {
if (dfs(board, word, i, j, 0, visited)) {
return true;
}
}
}
}
return false;
}
private boolean dfs(char[][] board, String word, int row, int col,
int index, boolean[][] visited) {
// Found complete word
if (index == word.length()) {
return true;
}
// Check boundaries
if (row < 0 || row >= board.length ||
col < 0 || col >= board[0].length) {
return false;
}
// Check if visited or character doesn't match
if (visited[row][col] || board[row][col] != word.charAt(index)) {
return false;
}
// Mark as visited
visited[row][col] = true;
// Try all 4 directions
for (int[] dir : directions) {
int newRow = row + dir[0];
int newCol = col + dir[1];
if (dfs(board, word, newRow, newCol, index + 1, visited)) {
return true;
}
}
// Backtrack - unmark
visited[row][col] = false;
return false;
}
public static void main(String[] args) {
Solution sol = new Solution();
char[][] board = {
{'A','B','C','E'},
{'S','F','C','S'},
{'A','D','E','E'}
};
System.out.println(sol.exist(board, "ABCCED")); // true
System.out.println(sol.exist(board, "SEE")); // true
System.out.println(sol.exist(board, "ABCB")); // false
}
}
⏰ Time: O(m × n × 4^L) where m×n = board size, L = word length
💾 Space: O(m × n) for visited array + O(L) recursion
🎯 Approach 2: Backtracking with In-Place Marking ⭐
Space-Optimized Solution
Idea: Instead of visited array, temporarily modify board to mark visited cells.
class Solution {
private int[][] directions = {{-1,0}, {1,0}, {0,-1}, {0,1}};
public boolean exist(char[][] board, String word) {
int m = board.length;
int 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)) {
if (dfs(board, word, i, j, 0)) {
return true;
}
}
}
}
return false;
}
private boolean dfs(char[][] board, String word, int row, int col, int index) {
if (index == word.length()) {
return true;
}
if (row < 0 || row >= board.length ||
col < 0 || col >= board[0].length ||
board[row][col] != word.charAt(index)) {
return false;
}
// Mark as visited by replacing with special character
char temp = board[row][col];
board[row][col] = '#';
// Try all 4 directions
for (int[] dir : directions) {
if (dfs(board, word, row + dir[0], col + dir[1], index + 1)) {
board[row][col] = temp; // Restore before returning
return true;
}
}
// Backtrack - restore original character
board[row][col] = temp;
return false;
}
}
Pros: O(L) space instead of O(m×n)
Cons: Modifies input (but restores it)
🔄 Is Backtracking the Only Way? What About Other Approaches?
Quick Answer: Backtracking is THE Standard Solution
For Word Search (LC 79):
✓ Backtracking (DFS): Standard, expected, optimal
✗ BFS: Possible but inefficient and complex
✗ Dynamic Programming: Not applicable
✗ Trie: Only for Word Search II (multiple words)
Bottom Line: Backtracking is not just common - it's THE solution!
Why Other Approaches Don't Work Well
BFS (Breadth-First Search):
❌ Theoretically possible but IMPRACTICAL
Problems:
1. Need to track entire path (not just distance)
2. State explosion: (row, col, index, visited_set)
3. Each state needs copy of visited cells
4. Memory intensive: O(4^L × m × n)
5. No practical advantage over DFS
Example complexity:
DFS: Each cell explored with O(L) depth
BFS: Need to store ALL partial paths simultaneously
For word length L=10:
DFS: O(m×n×4^10) time, O(10) space
BFS: O(m×n×4^10) time, O(4^10) space!
Interviewer reaction:
"Why are you using BFS? DFS is much simpler here."
Dynamic Programming:
❌ NOT APPLICABLE
Why DP doesn't work:
1. No optimal substructure
- Finding "ABC" doesn't help find "ABCD" at different position
2. No overlapping subproblems
- Each path is unique (different visited cells)
3. Need to track visited state
- DP can't handle "can't reuse cells" constraint easily
This is a PATH problem, not an OPTIMIZATION problem.
DP works for: "How many ways?" "Min/Max cost?"
Not for: "Does path exist?"
Trie (Prefix Tree):
✓ ONLY for Word Search II (LC 212)
Word Search (single word):
❌ Overkill, no benefit
- Building Trie: O(L) time
- DFS with Trie: Same complexity as plain DFS
- Added complexity: Not worth it
Word Search II (multiple words):
✓ Essential!
- Share prefix checking across words
- Prune searches early
- Much faster than checking each word separately
Comparison Table
┌──────────────────┬─────────────┬─────────────┬──────────────┐
│ Approach │ Applicable? │ Complexity │ Use Case │
├──────────────────┼─────────────┼─────────────┼──────────────┤
│ DFS Backtracking │ ✓ YES │ O(m×n×4^L) │ Single word │
│ BFS │ ✗ NO │ O(4^L) space│ Never │
│ Dynamic Prog. │ ✗ NO │ N/A │ Never │
│ Trie │ ✗ NO* │ Same as DFS │ Multi-word** │
└──────────────────┴─────────────┴─────────────┴──────────────┘
* Only useful for Word Search II
** Problem 212: Word Search II
What Interviewers Expect
Standard Question:
Interviewer: "Find if word exists in grid"
Expected: DFS + Backtracking
Follow-up Questions (that might come):
1. "Can you optimize this?"
Answer: "Not really - we must check all starting positions
and explore all paths. Already optimal O(m×n×4^L)."
2. "What if we have multiple words to search?"
Answer: "Then I'd use a Trie! Word Search II.
Build Trie of all words, DFS once, check multiple words.
Much better than checking each word separately."
3. "Can you do it iteratively?"
Answer: "Yes, using explicit stack instead of recursion.
But recursive DFS is cleaner and standard."
4. "What about BFS?"
Answer: "Possible but impractical - need to store all partial
paths. DFS is much more space-efficient here."
Interview Strategy
STEP 1: Immediately recognize it's DFS + Backtracking
"This is a classic DFS backtracking problem on a 2D grid."
STEP 2: Explain the approach
"I'll try starting from each cell that matches the first letter,
then use DFS to explore 4 directions, marking visited cells,
and backtracking when needed."
STEP 3: Implement DFS with visited tracking
STEP 4: If asked about alternatives
"For a single word, DFS is the standard solution.
Other approaches like BFS are possible but less efficient.
If we had multiple words, I'd use a Trie (Word Search II)."
Real Interview Scenario
Interviewer: "Given a grid and word, check if word exists."
❌ WRONG Response:
"Let me think about DP..."
"Should I use BFS?"
"Can I use Dijkstra?"
✓ CORRECT Response:
"This is DFS backtracking. I'll:
1. Try each cell as starting point
2. DFS with 4 directions
3. Track visited cells
4. Backtrack when needed"
Confidence is key!
The Two Valid Approaches (Both DFS!)
Approach 1: Visited Array (More Clear)
✓ Separate boolean[][] visited
✓ Explicit tracking
✓ Doesn't modify input
✓ Easier to debug
Space: O(m×n)
Approach 2: In-Place Marking (More Efficient)
✓ Modify board[i][j] temporarily
✓ Mark with '#' or special char
✓ Restore after backtracking
✓ Less space
Space: O(L) - just recursion
Both are DFS backtracking!
Both equally valid in interviews!
Why DFS Backtracking is Perfect Here
✓ Natural fit for path finding
✓ Easy to track visited cells (mark/unmark)
✓ Explores all possibilities efficiently
✓ Base case is clear (index == word.length)
✓ Prunes impossible paths early
✓ Space efficient (recursion depth = word length)
✓ Standard solution taught everywhere
This is THE textbook DFS backtracking problem!
Follow-up: Word Search II (Where Trie Matters)
Word Search II (LC 212):
Input: board, words = ["oath", "pea", "eat", "rain"]
Naive approach: Run Word Search for each word
Time: O(words.length × m × n × 4^L)
Trie approach: Build Trie, DFS once
Time: O(m × n × 4^L)
Much better!
This is when Trie becomes essential!
My Recommendation
DEFAULT: DFS Backtracking with Visited Array
Why?
1. THE standard solution
2. Everyone expects this
3. Clean and readable
4. Easy to explain
5. Optimal complexity
6. No alternatives are better
If interviewer asks "Can you do it differently?":
→ In-place marking (still DFS!)
→ Iterative DFS with stack (still same approach!)
If they say "What about multiple words?":
→ "That's Word Search II - I'd use a Trie!"
Bottom line: This IS a backtracking problem.
No other approach is expected or better.
Code Template You Must Know
// THIS is what interviewers expect:
private int[][] dirs = {{-1,0}, {1,0}, {0,-1}, {0,1}};
public boolean exist(char[][] board, String word) {
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
if (board[i][j] == word.charAt(0)) {
if (dfs(board, word, i, j, 0, new boolean[board.length][board[0].length])) {
return true;
}
}
}
}
return false;
}
private boolean dfs(char[][] board, String word, int row, int col,
int index, boolean[][] visited) {
if (index == word.length()) return true;
if (row < 0 || row >= board.length || col < 0 || col >= board[0].length) return false;
if (visited[row][col] || board[row][col] != word.charAt(index)) return false;
visited[row][col] = true;
for (int[] dir : dirs) {
if (dfs(board, word, row + dir[0], col + dir[1], index + 1, visited)) {
return true;
}
}
visited[row][col] = false;
return false;
}
Summary
Question: "Are there other approaches besides backtracking?"
Answer: "Technically yes, but practically NO.
✓ Backtracking (DFS) is THE solution
- Standard, expected, optimal
- Two variations: visited array or in-place marking
✗ Other approaches (BFS, DP, Trie) either:
- Don't apply (DP)
- Are impractical (BFS)
- Are overkill (Trie for single word)
This is a textbook DFS backtracking problem.
No interviewer expects anything else.
Safe to proceed with DFS backtracking with confidence!"
⚠️ Common Mistakes
Mistake 1: Not marking cell as visited
// ❌ WRONG - Can reuse same cell!
if (dfs(board, word, newRow, newCol, index + 1, visited)) {
return true;
}
// Doesn't mark visited[row][col] = true!
// ✓ CORRECT - Mark before exploring
visited[row][col] = true;
// Try all directions...
visited[row][col] = false; // Unmark after
Mistake 2: Not backtracking (unmarking)
// ❌ WRONG - Cell stays marked forever!
visited[row][col] = true;
for (int[] dir : directions) {
if (dfs(...)) return true;
}
return false; // Didn't unmark!
// ✓ CORRECT - Unmark after trying all paths
visited[row][col] = true;
for (int[] dir : directions) {
if (dfs(...)) return true;
}
visited[row][col] = false; // Backtrack!
return false;
Mistake 3: Wrong base case order
// ❌ WRONG - Checks bounds before index
if (row < 0 || row >= m || col < 0 || col >= n) return false;
if (index == word.length()) return true;
// Will return false when word is complete at boundary!
// ✓ CORRECT - Check completion first
if (index == word.length()) return true;
if (row < 0 || row >= m || col < 0 || col >= n) return false;
Mistake 4: Not restoring board in in-place approach
// ❌ WRONG - Board stays modified!
board[row][col] = '#';
for (int[] dir : directions) {
if (dfs(...)) return true; // Returns without restoring!
}
board[row][col] = temp;
return false;
// ✓ CORRECT - Restore before every return
board[row][col] = '#';
for (int[] dir : directions) {
if (dfs(...)) {
board[row][col] = temp; // Restore!
return true;
}
}
board[row][col] = temp;
return false;
Mistake 5: Forgetting to check character match
// ❌ WRONG - Doesn't validate character
if (visited[row][col]) return false;
visited[row][col] = true;
// Continues without checking board[row][col] == word.charAt(index)!
// ✓ CORRECT - Check character match
if (visited[row][col] || board[row][col] != word.charAt(index)) {
return false;
}
🎯 Pattern Recognition
Problem Type: 2D Grid Path Finding
Core Pattern: DFS + Backtracking + Visited Tracking
When to Apply:
✓ Search for path/sequence in 2D grid
✓ Can't reuse cells in same path
✓ Need to explore multiple possible paths
✓ 4-directional movement (up/down/left/right)
Recognition Keywords:
- "grid of characters"
- "sequentially adjacent cells"
- "same cell not used more than once"
- "horizontally or vertically neighboring"
- "exists in the grid"
Similar Problems:
- Word Search II (LC 212) - Multiple words with Trie
- Number of Islands (LC 200) - Connected components
- Surrounded Regions (LC 130) - Flood fill
- Pacific Atlantic Water Flow (LC 417) - Multi-source BFS/DFS
Key Components:
┌────────────────────────────────────────────┐
│ DFS: Explore paths recursively │
│ 4 Directions: Up, Down, Left, Right │
│ Visited: Track used cells (avoid reuse) │
│ Backtrack: Unmark when returning │
│ Base case: index == word.length │
│ Time: O(m×n×4^L), Space: O(m×n) or O(L) │
└────────────────────────────────────────────┘
🧠 Interview Strategy
Step 1: "This is a 2D grid search with backtracking"
Step 2: "I'll try DFS from each cell matching first letter"
Step 3: "Use visited array to prevent reusing cells"
Key Points to Mention:
- Try starting from every cell that matches word[0]
- DFS explores 4 directions (up, down, left, right)
- Mark cell as visited before exploring
- Unmark when backtracking (crucial!)
- Stop when complete word found
Walk Through Example:
"For board with word 'ABCCED':
Find 'A' at (0,0) → Start DFS
From (0,0), look for 'B' in 4 directions
Found at (0,1) → Continue
From (0,1), look for 'C'
Found at (0,2) → Continue
From (0,2), look for 'C'
Found at (1,2) → Continue
From (1,2), look for 'E'
Found at (2,2) → Continue
From (2,2), look for 'D'
Found at (2,1) → Complete! Return true"
Why Backtracking Needed:
"Imagine word is 'ABCB':
Path: A → B → C
Need 'B' again but (0,1) is marked visited
Can't find 'B' → Backtrack!
Unmark (0,2), try other paths from (0,1)
If all fail, unmark (0,1), try from different start"
Complexity:
"Time: O(m × n × 4^L)
- Try m×n starting positions
- From each, explore up to 4^L paths
- L is word length (branching factor 4)
Space: O(m×n) for visited array
- Or O(L) if modify board in-place
- Recursion depth: O(L)"
Two Approaches:
"1. Visited array: Clear, doesn't modify input
2. In-place marking: Less space, modifies board
Both same time complexity"
Edge Cases:
✓ Word not in board → false
✓ Word longer than board → false
✓ Single cell board → check if matches
✓ Word requires all cells → might work!
📝 Quick Revision Notes
🎯 Core Concept:
Word Search: Find if word exists in 2D grid by moving horizontally/vertically. Use DFS + Backtracking with visited tracking. Try starting from every cell matching word[0]. Mark cell visited, explore 4 directions, unmark when backtracking. Return true if index == word.length.
⚡ Quick Implementation:
public class Solution {
public boolean exist(char[][] board, String word) {
// return backtracking(board, word);
return backtrackingWithoutVisited(board, word);
}
private boolean backtrackingWithoutVisited(char[][] board, String word) {
// Approach
// Try DFS at each cell (i, j)
int m = board.length;
int n = board[0].length;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
// step 1: start DFS at each cell
if (dfsWithoutVisited(board, word, i, j, 0, m, n)) {
return true;
}
}
}
return false;
}
private boolean dfsWithoutVisited(char[][] board, String word, int currRow, int currCol, int currIndex, int m,
int n) {
// step 2: check if we reached the end of the word
if (currIndex == word.length()) {
return true;
}
// step 3: boundary checks
if (currRow < 0 || currRow >= m || currCol < 0 || currCol >= n) {
return false;
}
// step 4: check visited status
if (board[currRow][currCol] == '#') {
return false;
}
// step 5: check char now
if (word.charAt(currIndex) != board[currRow][currCol]) {
return false;
}
// step 6: take back up of current char and mark it as
// visited with a '#' character
char temp = board[currRow][currCol];
board[currRow][currCol] = '#';
// step 7: do DFS in all directions now for next character from the current cell
int[][] directions = new int[][] { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
for (int[] dir : directions) {
if (dfsWithoutVisited(board, word, currRow + dir[0], currCol + dir[1], currIndex + 1, m, n)) {
return true;
}
}
// step 8: mark it back as unvisited
board[currRow][currCol] = temp;
return false;
}
private boolean backtracking(char[][] board, String word) {
// Approach
// Try DFS at each cell (i, j)
int m = board.length;
int n = board[0].length;
boolean[][] visited = new boolean[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
// step 1: start DFS at each cell
if (dfs(board, word, i, j, 0, m, n, visited)) {
return true;
}
}
}
return false;
}
private boolean dfs(char[][] board, String word, int currRow, int currCol, int currIndex, int m, int n,
boolean[][] visited) {
// step 2: check if we reached the end of the word
if (currIndex == word.length()) {
return true;
}
// step 3: boundary checks
if (currRow < 0 || currRow >= m || currCol < 0 || currCol >= n) {
return false;
}
// step 4: check visited status
if (visited[currRow][currCol]) {
return false;
}
// step 5: check char now
if (word.charAt(currIndex) != board[currRow][currCol]) {
return false;
}
// step 6: mark it as visited
visited[currRow][currCol] = true;
// step 7: do DFS in all directions now for next character from the current cell
int[][] directions = new int[][] { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
for (int[] dir : directions) {
if (dfs(board, word, currRow + dir[0], currCol + dir[1], currIndex + 1, m, n, visited)) {
return true;
}
}
// step 8: mark it back as unvisited
visited[currRow][currCol] = false;
return false;
}
public static void main(String[] args) {
Solution s = new Solution();
System.out.println(
s.exist(new char[][] { { 'A', 'B', 'C', 'E' }, { 'S', 'F', 'C', 'S' }, { 'A', 'D', 'E', 'E' } }, "ABCCED"));
}
}
🔑 Key Insights:
- Pattern: DFS + Backtracking on 2D Grid
- 4 Directions: {{-1,0}, {1,0}, {0,-1}, {0,1}}
- Visited Tracking: Prevent cell reuse in same path
- Backtracking: MUST unmark visited[row][col] = false
- Try All Starts: Test every cell matching word[0]
- Time: O(m×n×4^L), Space: O(m×n) or O(L) ✓
🎪 Memory Aid:
"Mark visited, try four ways, unmark when done!"
"DFS the grid, backtrack the path!" ✨
⚠️ Critical Backtracking:
Without backtracking:
Mark (0,2) as visited
Try all paths, none work
Return false
(0,2) STAYS marked! ✗
Can never use this cell in other paths!
With backtracking:
Mark (0,2) as visited
Try all paths, none work
UNMARK (0,2) before returning ✓
(0,2) available for other paths!
ALWAYS unmark before returning false!
🎯 Two Space Approaches:
Approach 1: Visited Array
boolean[][] visited = new boolean[m][n];
visited[row][col] = true;
// explore...
visited[row][col] = false;
Space: O(m×n)
Pros: Clean, doesn't modify input
Cons: Extra space
Approach 2: In-Place Marking
char temp = board[row][col];
board[row][col] = '#'; // Mark
// explore...
board[row][col] = temp; // Restore
Space: O(L) (just recursion)
Pros: Space efficient
Cons: Modifies input (but restores)
Both: Same time complexity O(m×n×4^L)
🧪 Edge Cases
Case 1: Word not in board
Board: [['A','B'],['C','D']]
Word: "XYZ"
Output: false
No 'X' to start
Case 2: Single cell
Board: [['A']]
Word: "A"
Output: true
Matches immediately
Case 3: Word uses all cells
Board: [['A','B'],['C','D']]
Word: "ABDC"
Output: true
Path: (0,0)→(0,1)→(1,1)→(1,0)
Case 4: Word requires backtracking
Board: [['A','B','C'],['A','E','D']]
Word: "ABCEDA"
Output: true
Must backtrack from wrong paths
All handled correctly! ✓
🎓 Complexity Analysis
Time Complexity: O(m × n × 4^L)
Where:
m = number of rows
n = number of columns
L = length of word
Why?
Starting positions: m × n cells to try
From each start:
At each level, branch up to 4 ways
(up, down, left, right)
Maximum depth: L (length of word)
Branches: 4^L in worst case
Total: m × n × 4^L
Example:
m=3, n=4, L=6
3 × 4 × 4^6 = 12 × 4096 = 49,152 operations
Note: Pruning (visited check) reduces actual complexity
But worst case is still O(m×n×4^L)
Space Complexity: O(m × n) or O(L)
Approach 1 (Visited Array):
Visited array: O(m × n)
Recursion stack: O(L)
Total: O(m × n)
Approach 2 (In-Place):
No visited array: O(1)
Recursion stack: O(L)
Total: O(L)
Recursion depth = word length L
(One call per character in word)
📚 Related Problems
Same Core Pattern: - Word Search II (LC 212) - Multiple words (use Trie!) - Surrounded Regions (LC 130) - Flood fill with DFS - Number of Islands (LC 200) - Count connected components
Similar Grid DFS: - Pacific Atlantic Water Flow (LC 417) - Multi-source DFS - Walls and Gates (LC 286) - Multi-source BFS - Island Perimeter (LC 463) - DFS on grid
Backtracking on Grid: - Unique Paths III (LC 980) - Visit all cells - N-Queens (LC 51) - Place queens on board
Happy practicing! 🎯
Note: This is the classic 2D grid backtracking problem! Master this and you understand: (1) DFS on 2D grids, (2) marking/unmarking visited cells, (3) backtracking on spatial problems, (4) 4-directional movement. This pattern appears everywhere: maze solving, path finding, flood fill, connected components! Very common at FAANG - tests both DFS understanding and backtracking mastery! 💪✨