Word Search
Word Search is LeetCode 79 (Medium). You get an m × n grid of letters, board, and a string word. Return true if the word can be spelled by a path through the grid, and false otherwise.
The rules for the path:
- It starts on any cell holding the word's first letter.
- Each next letter must sit in a cell horizontally or vertically adjacent to the previous one. Diagonal steps are not allowed.
- No cell may be used twice in the same path.
You only need to report whether such a path exists, not where it is or how many there are.
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.
02
Intuition
In the word search LeetCode problem, a path is a chain of choices: from each cell there are up to four places to go next. Depth-first search walks that tree of choices one branch at a time, and a wrong letter kills a branch at once, which keeps the search fast in practice. That is why word search backtracking is the standard answer.
The no cell twice rule is a property of one path, not of the board. So a cell is marked while it is on the current path and unmarked the moment the search leaves it: mark on the way in, restore on the way out. Another branch or another start may need that same letter later.
How to spot this pattern
A grid, a sequence to trace through it, and a ban on reusing cells within one path. That is word search grid DFS: depth-first because a path is built one step at a time and abandoned as a unit, with a per-path visited mark that is undone on return. Flood fill (Number of Islands) marks cells and never unmarks them, because there a cell belongs to one island for good; here a cell belongs to a path only while that path is alive.
03
Approach
Try it first
Before reading on, decide what the recursive call needs to know, what it rejects immediately, and exactly when a cell's mark is removed. Aim for O(m·n·3^L) time and O(L) extra space, where L is the word length.
1
Try every cell as a starting point
Scan the grid in row order and start a search from each cell. A cell that does not hold word[0] fails the first check at once, so this costs O(1) per wrong cell. Return true as soon as one start succeeds.
2
Reject first, then recurse
dfs(r, c, k) asks: can word[k:] be spelled starting at (r, c)? Return false straight away if the cell is off the grid or does not hold word[k]; a cell marked '#' fails this same test. If k is the last index, the whole word is matched: return true.
3
Mark, try four neighbours, restore
- Write
'#'into the cell so this path cannot reuse it. - Call
dfson the cells up, down, left and right withk + 1, stopping at the firsttrue. - Write
word[k]back into the cell before returning, whatever the result.
The board doubles as the visited set, so no extra memory is needed beyond the recursion stack.
4
Prune before searching (optional speed-ups)
- If the word is longer than
m × n, returnfalsewithout searching. - Count letters: if the board has fewer copies of some letter than the word needs, no path can exist.
- If the word's last letter is rarer on the board than its first, reverse the word. Fewer starting cells means fewer doomed searches.
04
Word Search solution in Python | C++ | Java
▶1class Solution:
▶2 def exist(self, board: List[List[str]], word: str) -> bool:
▶3 R, C = len(board), len(board[0])
▶4 if len(word) > R * C:
▶5 return False
▶6
▶7 def dfs(r: int, c: int, k: int) -> bool:
▶8 if not (0 <= r < R and 0 <= c < C) or board[r][c] != word[k]:
▶9 return False
▶10 if k == len(word) - 1:
▶11 return True
▶12 board[r][c] = "#"
▶13 found = any(dfs(r + dr, c + dc, k + 1)
▶14 for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)))
▶15 board[r][c] = word[k]
▶16 return found
▶17
▶18 for r in range(R):
▶19 for c in range(C):
▶20 if dfs(r, c, 0):
▶21 return True
▶22 return False
▶1class Solution {
▶2public:
▶3 bool exist(vector<vector<char>>& board, string word) {
▶4 R = board.size();
▶5 C = board[0].size();
▶6 if ((int)word.size() > R * C) return false;
▶7 for (int r = 0; r < R; r++)
▶8 for (int c = 0; c < C; c++)
▶9 if (dfs(board, word, r, c, 0)) return true;
▶10 return false;
▶11 }
▶12
▶13private:
▶14 int R, C;
▶15 bool dfs(vector<vector<char>>& board, const string& word, int r, int c, int k) {
▶16 if (r < 0 || r >= R || c < 0 || c >= C || board[r][c] != word[k])
▶17 return false;
▶18 if (k == (int)word.size() - 1) return true;
▶19 board[r][c] = '#';
▶20 bool found = dfs(board, word, r - 1, c, k + 1) || dfs(board, word, r + 1, c, k + 1) ||
▶21 dfs(board, word, r, c - 1, k + 1) || dfs(board, word, r, c + 1, k + 1);
▶22 board[r][c] = word[k];
▶23 return found;
▶24 }
▶25};
▶1class Solution {
▶2 private int R, C;
▶3
▶4 public boolean exist(char[][] board, String word) {
▶5 R = board.length;
▶6 C = board[0].length;
▶7 if (word.length() > R * C) return false;
▶8 for (int r = 0; r < R; r++)
▶9 for (int c = 0; c < C; c++)
▶10 if (dfs(board, word, r, c, 0)) return true;
▶11 return false;
▶12 }
▶13
▶14 private boolean dfs(char[][] board, String word, int r, int c, int k) {
▶15 if (r < 0 || r >= R || c < 0 || c >= C || board[r][c] != word.charAt(k))
▶16 return false;
▶17 if (k == word.length() - 1) return true;
▶18 board[r][c] = '#';
▶19 boolean found = dfs(board, word, r - 1, c, k + 1) || dfs(board, word, r + 1, c, k + 1)
▶20 || dfs(board, word, r, c - 1, k + 1) || dfs(board, word, r, c + 1, k + 1);
▶21 board[r][c] = word.charAt(k);
▶22 return found;
▶23 }
▶24}
k0matched 'A'
cell(0,0)marked visited
depth1cells on the path
Anchor (0,0) holds 'A', the first letter, so a search starts here. The scan starts at the top-left cell. The code writes '#' over it to mark it visited, so this path cannot walk back onto it.
checkdown (1,0)needs 'B'
boardSwrong letter
Down (1,0) holds 'S', but the word needs 'B' here. The call returns false on its first check, so this branch costs O(1).
k1matched 'AB'
cell(0,1)marked visited
depth2cells on the path
Right (0,1) is 'B', letter 2 of 6, so the path extends. It is marked visited and the search looks for 'C' around it.
checkdown (1,1)needs 'C'
boardFwrong letter
Down (1,1) holds 'F', but the word needs 'C' here. The call returns false on its first check, so this branch costs O(1).
checkleft (0,0)needs 'C'
boardvisitedalready on this path
Left (0,0) is on this path already, so it is marked visited. The call returns false straight away.
k2matched 'ABC'
cell(0,2)marked visited
depth3cells on the path
Right (0,2) is 'C', letter 3 of 6, so the path extends. It is marked visited and the search looks for 'C' around it.
k3matched 'ABCC'
cell(1,2)marked visited
depth4cells on the path
Down (1,2) is 'C', letter 4 of 6, so the path extends. It is marked visited and the search looks for 'E' around it.
checkup (0,2)needs 'E'
boardvisitedalready on this path
Up (0,2) is on this path already, so it is marked visited. The call returns false straight away.
k4matched 'ABCCE'
cell(2,2)marked visited
depth5cells on the path
Down (2,2) is 'E', letter 5 of 6, so the path extends. It is marked visited and the search looks for 'D' around it.
checkup (1,2)needs 'D'
boardvisitedalready on this path
Up (1,2) is on this path already, so it is marked visited. The call returns false straight away.
k5last index of the word
path6 cellseach used once
resulttrue
Left (2,1) is 'D', letter 6 of 6, the last one. Every letter is matched, so this call returns true and every caller returns true at once. The question is whether the word exists, so the scan stops here.
k0matched 'S'
cell(1,0)marked visited
depth1cells on the path
Anchor (1,0) holds 'S', the first letter, so a search starts here. Every earlier cell failed the first-letter check at once, which costs O(1) each. The code writes '#' over it to mark it visited, so this path cannot walk back onto it.
checkup (0,0)needs 'E'
boardAwrong letter
Up (0,0) holds 'A', but the word needs 'E' here. The call returns false on its first check, so this branch costs O(1).
checkdown (2,0)needs 'E'
boardAwrong letter
Down (2,0) holds 'A', but the word needs 'E' here. The call returns false on its first check, so this branch costs O(1).
checkright (1,1)needs 'E'
boardFwrong letter
Right (1,1) holds 'F', but the word needs 'E' here. The call returns false on its first check, so this branch costs O(1).
k0no way to continue with 'E'
cell(1,0)visited → 'S'
depth0anchor failed
Every neighbour of (1,0) has been tried, so this call returns false. Before it does, it writes 'S' back, so the cell is no longer visited. The anchor itself failed; every cell it touched is restored, so the next anchor searches a clean board.
k0matched 'S'
cell(1,3)marked visited
depth1cells on the path
Anchor (1,3) holds 'S', the first letter, so a search starts here. The previous anchor restored every cell it marked, so this search sees the original board. The code writes '#' over it to mark it visited, so this path cannot walk back onto it.
k1matched 'SE'
cell(0,3)marked visited
depth2cells on the path
Up (0,3) is 'E', letter 2 of 3, so the path extends. It is marked visited and the search looks for 'E' around it.
checkdown (1,3)needs 'E'
boardvisitedalready on this path
Down (1,3) is on this path already, so it is marked visited. The call returns false straight away.
checkleft (0,2)needs 'E'
boardCwrong letter
Left (0,2) holds 'C', but the word needs 'E' here. The call returns false on its first check, so this branch costs O(1).
k1no way to continue with 'E'
cell(0,3)visited → 'E'
depth1back to the caller
Every neighbour of (0,3) has been tried, so this call returns false. Before it does, it writes 'E' back, so the cell is no longer visited. A different branch of the caller may still need this cell, and it must find the real letter there.
k1matched 'SE'
cell(2,3)marked visited
depth2cells on the path
Down (2,3) is 'E', letter 2 of 3, so the path extends. It is marked visited and the search looks for 'E' around it.
checkup (1,3)needs 'E'
boardvisitedalready on this path
Up (1,3) is on this path already, so it is marked visited. The call returns false straight away.
k2last index of the word
path3 cellseach used once
resulttrue
Left (2,2) is 'E', letter 3 of 3, the last one. Every letter is matched, so this call returns true and every caller returns true at once. The question is whether the word exists, so the scan stops here.
k0matched 'C'
cell(0,2)marked visited
depth1cells on the path
Anchor (0,2) holds 'C', the first letter, so a search starts here. Every earlier cell failed the first-letter check at once, which costs O(1) each. The code writes '#' over it to mark it visited, so this path cannot walk back onto it.
k1matched 'CC'
cell(1,2)marked visited
depth2cells on the path
Down (1,2) is 'C', letter 2 of 3, so the path extends. It is marked visited and the search looks for 'B' around it.
checkup (0,2)needs 'B'
boardvisitedalready on this path
Up (0,2) is on this path already, so it is marked visited. The call returns false straight away.
checkdown (2,2)needs 'B'
boardEwrong letter
Down (2,2) holds 'E', but the word needs 'B' here. The call returns false on its first check, so this branch costs O(1).
checkleft (1,1)needs 'B'
boardFwrong letter
Left (1,1) holds 'F', but the word needs 'B' here. The call returns false on its first check, so this branch costs O(1).
checkright (1,3)needs 'B'
boardSwrong letter
Right (1,3) holds 'S', but the word needs 'B' here. The call returns false on its first check, so this branch costs O(1).
k1no way to continue with 'B'
cell(1,2)visited → 'C'
depth1back to the caller
Every neighbour of (1,2) has been tried, so this call returns false. Before it does, it writes 'C' back, so the cell is no longer visited. A different branch of the caller may still need this cell, and it must find the real letter there.
checkleft (0,1)needs 'C'
boardBwrong letter
Left (0,1) holds 'B', but the word needs 'C' here. The call returns false on its first check, so this branch costs O(1).
checkright (0,3)needs 'C'
boardEwrong letter
Right (0,3) holds 'E', but the word needs 'C' here. The call returns false on its first check, so this branch costs O(1).
k0no way to continue with 'C'
cell(0,2)visited → 'C'
depth0anchor failed
Every neighbour of (0,2) has been tried, so this call returns false. Before it does, it writes 'C' back, so the cell is no longer visited. The anchor itself failed; every cell it touched is restored, so the next anchor searches a clean board.
k0matched 'C'
cell(1,2)marked visited
depth1cells on the path
Anchor (1,2) holds 'C', the first letter, so a search starts here. The previous anchor restored every cell it marked, so this search sees the original board. The code writes '#' over it to mark it visited, so this path cannot walk back onto it.
k1matched 'CC'
cell(0,2)marked visited
depth2cells on the path
Up (0,2) is 'C', letter 2 of 3, so the path extends. The failed search marked this cell earlier. It reads 'C' again only because that search wrote the letter back on its way out. It is marked visited and the search looks for 'B' around it.
checkdown (1,2)needs 'B'
boardvisitedalready on this path
Down (1,2) is on this path already, so it is marked visited. The call returns false straight away.
k2last index of the word
path3 cellseach used once
resulttrue
Left (0,1) is 'B', letter 3 of 3, the last one. Every letter is matched, so this call returns true and every caller returns true at once. The question is whether the word exists, so the scan stops here.
k0matched 'A'
cell(0,0)marked visited
depth1cells on the path
Anchor (0,0) holds 'A', the first letter, so a search starts here. The scan starts at the top-left cell. The code writes '#' over it to mark it visited, so this path cannot walk back onto it.
checkdown (1,0)needs 'B'
boardSwrong letter
Down (1,0) holds 'S', but the word needs 'B' here. The call returns false on its first check, so this branch costs O(1).
k1matched 'AB'
cell(0,1)marked visited
depth2cells on the path
Right (0,1) is 'B', letter 2 of 4, so the path extends. It is marked visited and the search looks for 'C' around it.
checkdown (1,1)needs 'C'
boardFwrong letter
Down (1,1) holds 'F', but the word needs 'C' here. The call returns false on its first check, so this branch costs O(1).
checkleft (0,0)needs 'C'
boardvisitedalready on this path
Left (0,0) is on this path already, so it is marked visited. The call returns false straight away.
k2matched 'ABC'
cell(0,2)marked visited
depth3cells on the path
Right (0,2) is 'C', letter 3 of 4, so the path extends. It is marked visited and the search looks for 'B' around it.
checkdown (1,2)needs 'B'
boardCwrong letter
Down (1,2) holds 'C', but the word needs 'B' here. The call returns false on its first check, so this branch costs O(1).
checkleft (0,1)needs 'B'
boardvisitedalready on this path
Left (0,1) is on this path already, so it is marked visited. It really holds 'B', the letter needed, but using it would put one cell in the path twice, which the rules forbid. The call returns false straight away.
checkright (0,3)needs 'B'
boardEwrong letter
Right (0,3) holds 'E', but the word needs 'B' here. The call returns false on its first check, so this branch costs O(1).
k2no way to continue with 'B'
cell(0,2)visited → 'C'
depth2back to the caller
Every neighbour of (0,2) has been tried, so this call returns false. Before it does, it writes 'C' back, so the cell is no longer visited. A different branch of the caller may still need this cell, and it must find the real letter there.
k1no way to continue with 'C'
cell(0,1)visited → 'B'
depth1back to the caller
Every neighbour of (0,1) has been tried, so this call returns false. Before it does, it writes 'B' back, so the cell is no longer visited. A different branch of the caller may still need this cell, and it must find the real letter there.
k0no way to continue with 'B'
cell(0,0)visited → 'A'
depth0anchor failed
Every neighbour of (0,0) has been tried, so this call returns false. Before it does, it writes 'A' back, so the cell is no longer visited. The anchor itself failed; every cell it touched is restored, so the next anchor searches a clean board.
k0matched 'A'
cell(2,0)marked visited
depth1cells on the path
Anchor (2,0) holds 'A', the first letter, so a search starts here. The previous anchor restored every cell it marked, so this search sees the original board. The code writes '#' over it to mark it visited, so this path cannot walk back onto it.
checkup (1,0)needs 'B'
boardSwrong letter
Up (1,0) holds 'S', but the word needs 'B' here. The call returns false on its first check, so this branch costs O(1).
checkright (2,1)needs 'B'
boardDwrong letter
Right (2,1) holds 'D', but the word needs 'B' here. The call returns false on its first check, so this branch costs O(1).
k0no way to continue with 'B'
cell(2,0)visited → 'A'
depth0anchor failed
Every neighbour of (2,0) has been tried, so this call returns false. Before it does, it writes 'A' back, so the cell is no longer visited. The anchor itself failed; every cell it touched is restored, so the next anchor searches a clean board.
anchors2cells holding 'A'
resultfalse
Every anchor was tried and every branch dead-ended, so the word is not on the board and the answer is false. The board is back to its original letters: each call restored its own cell before returning.
05
Common pitfalls
Marking a cell and never restoring it
✗ Wrong
board[r][c] = "#" found = any(dfs(r + dr, c + dc, k + 1) for dr, dc in DIRS) return found
✓ Right
board[r][c] = "#" found = any(dfs(r + dr, c + dc, k + 1) for dr, dc in DIRS) board[r][c] = word[k] return found
On the sample board, "CCB" first starts at the top C, which fails. Without the restore that C stays '#', and the second start, which needs it as its second letter, is rejected. The answer comes out false although the word is there.
Searching with BFS and one shared visited set
✗ Wrong
seen = {(r, c)}
q = deque([(r, c, 0)])
while q:
... # mark each neighbour in seen when queued✓ Right
def dfs(r, c, k):
... # mark on entry, unmark on returnA cell can be reached by several partial paths, and only one of them may be the right one. BFS keeps one global seen, so the first partial path to claim a cell blocks every other path from using it. The no reuse rule is per path, and only DFS has a single current path to attach the mark to.
06
Edge cases
One-cell board
Success is detected on the cell that matches the last letter (k == len(word) - 1), not by stepping into a neighbour afterwards. A 1 × 1 board has no neighbour to step into, so the other order would return false for a one-letter word that is sitting right there.
07
Complexity
Time
O(m·n·3^L)
Space
O(L)
There are m·n starting cells. From the first cell the path has 4 choices, and after that at most 3, because the cell it came from is marked. So each start explores at most 4·3^(L-1) paths. Extra space is the recursion stack, one frame per matched letter; the board itself is the visited set.
08
Word Search vs look-alike grid problems
The grid and the DFS look the same in all three. What differs is how many words there are and whether a mark is ever undone.
| Problem | Question | Visited mark | Tool |
|---|---|---|---|
| Word Search (79) | Is this one word on the board? | Per path: set on entry, undone on return | DFS + backtracking |
| Word Search II (212) | Which of many words are on the board? | Per path, same as 79 | DFS guided by a trie of all words |
| Number of Islands (200) | How many connected land regions? | Permanent: a cell joins one island for good | Flood fill, no undo |
09
Word Search FAQ
How do you write word search in Python?
Define a nested dfs(r, c, k) that returns False for an out-of-range or mismatched cell, True when k is the last index, and otherwise marks the cell, uses any(...) over the four directions, restores the cell and returns the result. The outer loops call dfs(r, c, 0) for every cell. any stops at the first True, so no extra early-exit code is needed in word search in Python.