Word Search
Check whether a word can be traced through a letter grid by stepping between neighboring cells, never reusing a cell. Classic grid backtracking. Solve it below in Python or JavaScript, then read the walkthrough.
Problem
You're given an m × n grid of letters, board, and a string word. Return true if you can spell word by starting at some cell and repeatedly stepping to a cell that is directly up, down, left or right of the current one, and false otherwise.
Each cell can be used at most once in a single path. Letters are case-sensitive.
Example 1
- Input
- board = [["C","A","T","S"], ["O","R","E","P"], ["D","E","N","T"]], word = "SPENT"
- Output
- true
Start at S in the top-right corner, go down to P, left to E, down to N, and right to T.
Example 2
- Input
- same board, word = "RACE"
- Output
- false
R → A → C works, but the only neighbors of that C are A and O, so there is no E to step to.
Example 3
- Input
- same board, word = "CAC"
- Output
- false
The board has only one C, and a path can't visit the same cell twice.
Constraints
- 1 ≤ m, n ≤ 6
- 1 ≤ word.length ≤ 15
- board and word contain only uppercase and lowercase English letters.
Practice
Runs 13 tests in your browser. Python loads on the first run (about 6 MB, then cached). Press ⌘/Ctrl + Enter to run.
Get asked Word Search in a real interview?
Interview Solver gives you a working solution live, during your actual coding interview. Invisible to screensharing.
How to solve Word Search
Pattern: Grid backtracking (DFS)
"Find a path through a grid, with no cell used twice" is the signature of backtracking. From any cell you have up to four choices, and a wrong choice is only discovered several steps later, so you need to explore a branch, and if it dead-ends, undo it and try the next.
The undo step is what makes the "no reuse" rule work. Mark a cell as used when you step onto it, and unmark it when you return. That way a cell blocked on one path is free again for a different path through the same area.
Because the search can blow up on boards full of the same letter, cheap checks before searching pay off: if the word is longer than the board, or needs more of some letter than the board has, the answer is false without any search.
Approach 1: Enumerate paths with a visited set
Run DFS from every cell, carrying a separate copy of the visited set (or the path so far) down each branch. Correct, but copying the set at each step adds O(L) work per call and lots of memory churn.
Time O(m · n · 3^L · L) · Space O(L²)
Approach 2: Backtracking with in-place marking and pruning
- If
wordis longer thanm · n, or any letter appears inwordmore often than on the board, return false. - For each cell, call
dfs(r, c, i):- If the cell is out of bounds or its letter isn't
word[i], return false. - If
iis the last index, return true. - Temporarily overwrite the cell with a marker like
#, recurse into the four neighbors withi + 1, then restore the letter.
- If the cell is out of bounds or its letter isn't
- Return true as soon as any start succeeds.
After the first step each cell has at most three unvisited neighbors to try, which is where the 3^L factor comes from.
Time O(m · n · 3^L) · Space O(L)
| Approach | Time | Space |
|---|---|---|
| Enumerate paths with a visited set | O(m · n · 3^L · L) | O(L²) |
| Backtracking with in-place marking and pruning | O(m · n · 3^L) | O(L) |
Solution code
Try the practice editor first. Both solutions pass every test above.
Word Search solution in Python
from collections import Counter
def exist(board: list[list[str]], word: str) -> bool:
rows, cols = len(board), len(board[0])
if len(word) > rows * cols:
return False
on_board = Counter(ch for row in board for ch in row)
for ch, count in Counter(word).items():
if on_board[ch] < count:
return False
def dfs(r: int, c: int, i: int) -> bool:
if r < 0 or r >= rows or c < 0 or c >= cols or board[r][c] != word[i]:
return False
if i == len(word) - 1:
return True
board[r][c] = "#" # mark as used on this path
found = (
dfs(r + 1, c, i + 1)
or dfs(r - 1, c, i + 1)
or dfs(r, c + 1, i + 1)
or dfs(r, c - 1, i + 1)
)
board[r][c] = word[i] # restore for other paths
return found
return any(dfs(r, c, 0) for r in range(rows) for c in range(cols))Word Search solution in JavaScript
function exist(board, word) {
const rows = board.length;
const cols = board[0].length;
if (word.length > rows * cols) return false;
const onBoard = new Map();
for (const row of board) {
for (const ch of row) onBoard.set(ch, (onBoard.get(ch) || 0) + 1);
}
const needed = new Map();
for (const ch of word) needed.set(ch, (needed.get(ch) || 0) + 1);
for (const [ch, count] of needed) {
if ((onBoard.get(ch) || 0) < count) return false;
}
const dfs = (r, c, i) => {
if (r < 0 || r >= rows || c < 0 || c >= cols || board[r][c] !== word[i]) {
return false;
}
if (i === word.length - 1) return true;
board[r][c] = '#'; // mark as used on this path
const found =
dfs(r + 1, c, i + 1) ||
dfs(r - 1, c, i + 1) ||
dfs(r, c + 1, i + 1) ||
dfs(r, c - 1, i + 1);
board[r][c] = word[i]; // restore for other paths
return found;
};
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
if (dfs(r, c, 0)) return true;
}
}
return false;
}Common mistakes
- Forgetting to restore the cell after exploring it, which blocks it for every later path and gives false negatives.
- Marking the cell visited before checking whether it matches, then returning without unmarking it.
- Checking `i == len(word)` only after moving to a neighbor, which fails for a one-letter word on a one-cell board or reads past the grid edge.
- Allowing diagonal moves. Only the four orthogonal neighbors count.
- Continuing the search after a path is found instead of returning true immediately.
What interviewers look for
Name the technique ("DFS with backtracking") and the complexity bound before coding, and explain why it is exponential in the word length rather than the board size. Interviewers listen for the mark-and-restore step; say out loud when you set the marker and when you put the letter back.
Mentioning the letter-count pruning (and optionally searching from whichever end of the word is rarer on the board) shows you think about worst cases, not just the happy path.
Follow-up questions
How would you find every word from a dictionary that appears on the board?
Put the dictionary in a trie and run one DFS from each cell, walking the trie alongside the grid. You stop as soon as the current prefix isn't in the trie, and you can prune trie nodes once their words are found. Running the single-word search per word repeats a lot of work.
Why might reversing the word speed things up?
If the first letter is very common and the last is rare, starting from the rare end means far fewer starting cells survive the first step. Count both end letters on the board and search from the rarer one.
What if cells could be reused, but not consecutively?
Then no visited marking is needed, and the state is just (cell, index), so memoize it. That turns the search into DP over m · n · L states, each trying four neighbors.
Companies that ask Word Search
Word Search is tagged by 117 companies in our interview dataset. The score shows how often it comes up at each company.
- Basis Technologies100%
- F5 Networks100%
- Alnylam Pharmaceuticals100%
- Prove100%
- Blue Origin100%
- Faire100%
- Boston Scientific99%
- Springworks Therapeutics95%
- Coffee Meets Bagel95%
- Xilinx94%
- Gainsight92%
- Bloomreach91%
- Forto90%
- Atos90%
- Loblaw Digital89%
- General Atomics88%
- Cerebras Systems88%
- Karat87.8%
- Philips84%
- Rally Health83%
- Sigma Computing83%
- Skyworks Solutions83%
- CGI83%
- Zuora81%
and 93 more.
Practice next
Get live help in the real interview
Working solutions in real time during your actual interview. Invisible to screensharing.
Start Free TrialNo credit card required