#79 Word Search
frequently reported atUberBloombergByteDance / TikTokNetflixPayPalAmazon
the problem
In plain words
Given an m × n grid of letters and a word, return true if the word can be spelled by moving between horizontally or vertically adjacent cells, using each cell at most once.
in board = ["ABCE","SFCS","ADEE"], word = "ABCCED"
out true
in same board, word = "SEE"
out true
in same board, word = "ABCB"
out false
The only B next to C was already used.
- 1 ≤ m, n ≤ 6
- 1 ≤ word.length ≤ 15
- Upper- and lowercase English letters
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternBacktracking on a grid
DFS from every cell; a cell on the current path is temporarily 'used' and must be released when you backtrack — otherwise other paths can't use it.
solutions
From brute force to optimal
From each start cell, DFS to neighbours that match the next letter and aren't visited; unmark on return.
- For every (r, c): dfs(0, r, c).
- Mismatch → false; last letter matched → true.
- visited = true, try 4 neighbours, visited = false.
m·n starts; after the first step each cell has ≤ 3 unvisited neighbours, for L letters.
The visited grid plus recursion depth L.
class Solution { private static final int[][] DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; public boolean exist(char[][] board, String word) { int rows = board.length, cols = board[0].length; boolean[][] visited = new boolean[rows][cols]; for (int r = 0; r < rows; r++) for (int c = 0; c < cols; c++) if (dfs(board, word, 0, r, c, visited)) return true; return false; } private boolean dfs(char[][] board, String word, int k, int r, int c, boolean[][] visited) { if (board[r][c] != word.charAt(k)) return false; if (k == word.length() - 1) return true; // matched the last letter visited[r][c] = true; // choose this cell for (int[] d : DIRS) { int nr = r + d[0], nc = c + d[1]; if (nr >= 0 && nc >= 0 && nr < board.length && nc < board[0].length && !visited[nr][nc] && dfs(board, word, k + 1, nr, nc, visited)) { visited[r][c] = false; // tidy up even on success return true; } } visited[r][c] = false; // un-choose return false; }}Overwrite the cell with '#' while it's on the path (no visited grid), and reject early if the board lacks enough of some letter.
- Count board letters; if the word needs more of any letter → false.
- dfs: k == L → true; out of bounds or mismatch → false.
- Save, set '#', explore 4 directions, restore.
Same worst case; the count check is O(m·n + L) and often answers instantly.
Only recursion depth — the board itself stores the marks.
class Solution { public boolean exist(char[][] board, String word) { if (!enoughLetters(board, word)) return false; // cheap global pruning for (int r = 0; r < board.length; r++) for (int c = 0; c < board[0].length; c++) if (dfs(board, word, 0, r, c)) return true; return false; } private boolean dfs(char[][] board, String word, int k, int r, int c) { if (k == word.length()) return true; if (r < 0 || c < 0 || r >= board.length || c >= board[0].length || board[r][c] != word.charAt(k)) return false; // off board, wrong letter, or '#' char saved = board[r][c]; board[r][c] = '#'; // mark: this cell is on the path boolean ok = dfs(board, word, k + 1, r + 1, c) || dfs(board, word, k + 1, r - 1, c) || dfs(board, word, k + 1, r, c + 1) || dfs(board, word, k + 1, r, c - 1); board[r][c] = saved; // un-mark return ok; } private boolean enoughLetters(char[][] board, String word) { int[] count = new int[128]; for (char[] row : board) for (char ch : row) count[ch]++; for (char ch : word.toCharArray()) if (--count[ch] < 0) return false; return true; }}Dry run
in the room
How to say it in the interview
talk track
- Ask if modifying the board is allowed (restore it anyway).
- Mention the extra prune: if the first letter is more frequent than the last, search the reversed word — fewer starting points.
traps
- Not restoring the cell after a failed branch — later starts see a damaged board.
- Using a global visited set but never removing from it.
what they ask next
Follow-ups
Many words at once (LC 212 Word Search II)?
Put all words in a trie and run one DFS per cell walking the trie — avoids re-searching shared prefixes.
before you submit
Edge cases to test
- A one-cell board and a one-letter word.
- The word is longer than the number of cells → false.
- A cell can't be reused: ["aa"] with "aaa" → false.
- Upper- and lowercase letters are different.
practise next
Similar problems
- #212Word Search IIHardin Tries
- #200Number of IslandsMediumin Graphs
- #51N-QueensHardin Backtracking