Word Search
Problem
m x n grid of letters board and a string
word. Decide whether word can be spelled by a path of cells where each
step moves up, down, left or right. A single cell may be used at most once in the
path.board = [[A,B,C,E],[S,F,C,S],[A,D,E,E]], word = "ABCCED"Outputtruesame board, word = "SEE"Outputtruesame board, word = "ABCB"Outputfalse1 ≤ m, n ≤ 6 · 1 ≤ word.length ≤ 15 · upper- and lower-case English letters · Follow-up: prune the search for larger boards.
Try it yourself
class Solution {
public boolean exist(char[][] board, String word) {
}
}
Instinct Return ALL combinations, permutations, partitions or placements - or ask if any arrangement works - build a candidate step by step and undo each choice.
Memory hack Choose, explore, un-choose - walk the decision tree and snip a branch the moment it can no longer succeed.
Open the Backtracking guide →Approaches
Brute ForceDFS with a Copied Visited Set
O(m · n · 3L · L)Space O(L2)From each cell, explore all four neighbours for the next letter. To avoid reusing a cell, every call receives its own copy of the set of cells already on the path, so nothing ever has to be undone. Correct, but each step pays O(L) just to copy the set.
public boolean exist(char[][] board, String word) { for (int r = 0; r < board.length; r++) { for (int c = 0; c < board[0].length; c++) { if (dfs(board, word, r, c, 0, new HashSet<>())) return true; } } return false; } private boolean dfs(char[][] b, String w, int r, int c, int i, Set<Integer> seen) { if (i == w.length()) return true; if (r < 0 || c < 0 || r >= b.length || c >= b[0].length) return false; int key = r * b[0].length + c; if (seen.contains(key) || b[r][c] != w.charAt(i)) return false; Set<Integer> path = new HashSet<>(seen); // private copy for this branch path.add(key); return dfs(b, w, r + 1, c, i + 1, path) || dfs(b, w, r - 1, c, i + 1, path) || dfs(b, w, r, c + 1, i + 1, path) || dfs(b, w, r, c - 1, i + 1, path); }
No undo logic to get wrong, but the per-step set copies are pure overhead.
BetterBacktracking with a Visited Grid
O(m · n · 3L)Space O(m · n)Share one boolean[][] visited across the whole search. Mark the cell
before exploring its neighbours and clear it right after, so sibling branches see the
grid exactly as it was. After the first step each cell has at most 3 fresh neighbours,
hence 3L.
public boolean exist(char[][] board, String word) { boolean[][] visited = new boolean[board.length][board[0].length]; for (int r = 0; r < board.length; r++) { for (int c = 0; c < board[0].length; c++) { if (dfs(board, word, r, c, 0, visited)) return true; } } return false; } private boolean dfs(char[][] b, String w, int r, int c, int i, boolean[][] visited) { if (i == w.length()) return true; if (r < 0 || c < 0 || r >= b.length || c >= b[0].length) return false; if (visited[r][c] || b[r][c] != w.charAt(i)) return false; visited[r][c] = true; // mark boolean found = dfs(b, w, r + 1, c, i + 1, visited) || dfs(b, w, r - 1, c, i + 1, visited) || dfs(b, w, r, c + 1, i + 1, visited) || dfs(b, w, r, c - 1, i + 1, visited); visited[r][c] = false; // unmark return found; }
Classic backtracking with O(1) mark/unmark, but still allocates an m x n grid.
OptimalIn-Place Marking + Letter-Count Pruning
O(m · n · 3L)Space O(L)Mark a cell by temporarily overwriting it with '#' (which never matches a
letter) and restore it on return — no extra grid. Before searching, count letters:
if the board lacks enough of any letter, answer false immediately; and if the
word's last letter is rarer than its first, search the reversed word so the DFS
starts from fewer cells.
public boolean exist(char[][] board, String word) { int[] have = new int[128], need = new int[128]; for (char[] row : board) for (char ch : row) have[ch]++; for (char ch : word.toCharArray()) { if (++need[ch] > have[ch]) return false; // board can't supply this letter } // Start from the rarer end of the word if (have[word.charAt(word.length() - 1)] < have[word.charAt(0)]) { word = new StringBuilder(word).reverse().toString(); } for (int r = 0; r < board.length; r++) { for (int c = 0; c < board[0].length; c++) { if (dfs(board, word, r, c, 0)) return true; } } return false; } private boolean dfs(char[][] b, String w, int r, int c, int i) { if (i == w.length()) return true; if (r < 0 || c < 0 || r >= b.length || c >= b[0].length) return false; if (b[r][c] != w.charAt(i)) return false; // also rejects '#' char saved = b[r][c]; b[r][c] = '#'; // mark in place boolean found = dfs(b, w, r + 1, c, i + 1) || dfs(b, w, r - 1, c, i + 1) || dfs(b, w, r, c + 1, i + 1) || dfs(b, w, r, c - 1, i + 1); b[r][c] = saved; // restore return found; }
Same worst case, but O(L) memory and pruning that kills most hopeless searches early.
At a glance
| Level | Approach | Time | Space |
|---|---|---|---|
| Brute Force | DFS with a Copied Visited Set | O(m · n · 3L · L) | O(L2) |
| Better | Backtracking with a Visited Grid | O(m · n · 3L) | O(m · n) |
| Optimal | In-Place Marking + Letter-Count Pruning | O(m · n · 3L) | O(L) |
- Not unmarking a cell on backtrack — later branches think it is still in use.
- Checking the bounds after indexing
board[r][c]— index out of range. - Returning early on success before restoring the cell in the in-place version.
- State the search space: every start cell times at most 4 · 3L-1 paths.
- Offer in-place marking as the memory upgrade, and ask if mutating the input is allowed.
- Bring up the frequency check / reverse trick as the follow-up pruning answer.