Word Search
Asked at Atlassian, Netflix, Oracle, Walmart
Problem
Given an m x n grid of characters and a word, find if the word exists in the grid. The word can be constructed from letters of sequentially adjacent cells (horizontally or vertically). Each cell can only be used once per search. This is a classic backtracking / DFS problem on a grid.
Asked At
| Company | Difficulty | |
|---|---|---|
| Atlassian | Medium | View all Atlassian questions → |
| Netflix | Medium | View all Netflix questions → |
| Oracle | Medium | View all Oracle questions → |
| Walmart | Medium | View all Walmart questions → |
How to Think About It
Brute force: for every cell in the grid, start a DFS from that cell and try to match the entire word. That's O(m * n * 4^L) where L is the word length. Each cell has 4 directions, and you explore up to L levels deep.
Key insight: use backtracking. Start DFS from each cell that matches the first character. At each step, mark the current cell as visited (e.g., set to '#'), explore all 4 directions for the next character, then unmark when backtracking.
Why mark cells as visited: without marking, you might revisit the same cell in the same path, creating infinite loops. Setting the cell to a special character ('#') prevents revisiting. Unmarking when backtracking allows other paths to use this cell.
Pruning: if the current character doesn't match, stop immediately. You can also pre-check if the word's character counts exceed what's available in the grid, but that's an optimization, not required.
Visual walkthrough for grid = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]] and word = "ABCCED":
Start at (0,0)='A'. Match! Mark '#'
Go right to (0,1)='B'. Match! Mark '#'
Go right to (0,2)='C'. Match! Mark '#'
Go right to (0,3)='E'. No match (need 'C'). Backtrack.
Go down from (0,2) to (1,2)='C'. Match! Mark '#'
Go down from (1,2) to (2,2)='E'. No match (need 'E'... wait, next is 'E'). Match! Mark '#'
Word complete! Return true.
Edge cases: empty grid returns false. Empty word returns true. Word longer than grid size returns false. Word uses a character not in the grid returns false. Grid with one cell.
Optimal Approach
Step 1: For each cell (i, j) in the grid:
- If grid[i][j] matches word[0], start DFS from (i, j) with index 0
Step 2: DFS function at (i, j, index): - If index == len(word), return true (all characters matched)
- If (i, j) is out of bounds or grid[i][j] != word[index], return false
- Save grid[i][j], mark it as visited (set to a placeholder char)
- Recurse in all 4 directions with index + 1
- Unmark grid[i][j] (backtrack)
- Return true if any direction returned true
Walkthrough for grid [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word="ABCCED":
- Start DFS at (0,0)="A", index=0. Match. Mark visited.
- (0,1)="B", index=1. Match. Mark visited.
- (0,2)="C", index=2. Match. Mark visited.
- (0,3)="E", index=3. Need "C", got "E". Fail. Backtrack.
- (1,2)="C", index=3. Match. Mark visited.
- (2,2)="E", index=4. Need "E", got "E". Match. Mark visited.
- (2,1)="D", index=5. Need "D", got "D". Match. Index 6 == len(word). Return true.
Time: O(m * n * 4^L) worst case, but pruning makes it much faster in practice. Space: O(L) for the recursion stack (L = word length).
What Trips People Up in Real Interviews
Using a visited matrix instead of marking cells in-place. A separate visited matrix uses O(m*n) extra space. Marking cells with a placeholder character (like '#') and unmarking on backtrack is the standard in-place approach.
Forgetting to unmark (backtrack) after exploring a cell. If you don't restore the original character, other DFS paths from different starting cells can't use this cell, giving false negatives.
Trying to use BFS instead of DFS. BFS doesn't work well here because you need to track the exact path taken (which cells are in the current path). DFS naturally handles this with the call stack.
Not pruning early when the current character doesn't match. Without pruning, you explore all 4 directions even when the current cell doesn't match the needed character, wasting time.
Checking all 4 directions without short-circuit evaluation. Use if (dfs(...)) return true for each direction so you stop as soon as one path succeeds. Checking all directions unconditionally adds unnecessary work.
Solution Code
def exist(board, word):
if not board or not board[0]:
return False
rows, cols = len(board), len(board[0])
def dfs(r, c, idx):
if idx == len(word):
return True
if r < 0 or r >= rows or c < 0 or c >= cols or board[r][c] != word[idx]:
return False
temp = board[r][c]
board[r][c] = '#'
for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
if dfs(r+dr, c+dc, idx+1):
return True
board[r][c] = temp
return False
for r in range(rows):
for c in range(cols):
if dfs(r, c, 0):
return True
return FalseFrequently Asked Questions
What is the Word Search problem?
Given an m x n grid of characters and a word, find if the word exists in the grid. The word can be constructed from letters of sequentially adjacent cells (horizontally or vertically). Each cell can only be used once per search. This is a classic `backtracking` / `DFS` problem on a grid.
How do you solve Word Search?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Word Search?
Word Search is asked at Atlassian, Netflix, Oracle, Walmart. It is a medium difficulty problem.
What are common mistakes on Word Search?
- Using a `visited` matrix instead of marking cells in-place. A separate `visited` matrix uses `O(m*n)` extra space. Marking cells with a placeholder character (like '#') and unmarking on backtrack is the standard in-place approach.
- Forgetting to unmark (backtrack) after exploring a cell. If you don't restore the original character, other DFS paths from different starting cells can't use this cell, giving false negatives.
- Trying to use `BFS` instead of `DFS`. BFS doesn't work well here because you need to track the exact path taken (which cells are in the current path). DFS naturally handles this with the call stack.
- Not pruning early when the current character doesn't match. Without pruning, you explore all 4 directions even when the current cell doesn't match the needed character, wasting time.
- Checking all 4 directions without short-circuit evaluation. Use `if (dfs(...)) return true` for each direction so you stop as soon as one path succeeds. Checking all directions unconditionally adds unnecessary work.