Lesson 132 of 250
79. Word Search
NeetCode: Word Search · LeetCode: 79. Word Search · Difficulty: Medium
Given an m x n grid of characters board and a string word, return true if word exists in the grid. The word is built from letters of sequentially adjacent cells (up, down, left, right), and the same cell may not be used more than once.
Example
board = [["A","B","C","E"],
["S","F","C","S"],
["A","D","E","E"]]
word = "ABCCED" Output: true
word = "SEE" Output: true
word = "ABCB" Output: falseBrute force: DFS with a list of visited cells
Try every cell as the start. From a cell that matches the current letter, recurse into the four neighbours for the next letter. To respect "no reuse", keep the current path as a list of cell numbers (r * cols + c) and check path.contains(..) before entering a cell. Every visit pays an O(L) scan of the path, and the search continues even when the board cannot contain the word.
LeetCode's Java signature is boolean exist(char[][] board, String word). The path is a List<Integer>: contains compares boxed values with equals, so it finds a cell number by value. (A List<int[]> would not work, because arrays compare by identity.) The grid helper in main builds a char[][] from row strings.
import java.util.ArrayList;
import java.util.List;
public class Main {
static class Solution {
private static final int[][] DIRS = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
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, 0, r, c, new ArrayList<>())) {
return true;
}
}
}
return false;
}
private boolean dfs(char[][] board, String word, int idx, int r, int c, List<Integer> path) {
if (idx == word.length()) {
return true;
}
if (r < 0 || c < 0 || r >= board.length || c >= board[0].length) {
return false;
}
Integer cell = r * board[0].length + c;
if (board[r][c] != word.charAt(idx) || path.contains(cell)) {
return false;
}
path.add(cell);
for (int[] d : DIRS) {
if (dfs(board, word, idx + 1, r + d[0], c + d[1], path)) {
return true;
}
}
path.remove(path.size() - 1);
return false;
}
}
static char[][] grid(String... rows) {
char[][] g = new char[rows.length][];
for (int i = 0; i < rows.length; i++) {
g[i] = rows[i].toCharArray();
}
return g;
}
public static void main(String[] args) {
Solution s = new Solution();
char[][] board = grid("ABCE", "SFCS", "ADEE");
System.out.println(s.exist(board, "ABCCED"));
System.out.println(s.exist(board, "SEE"));
System.out.println(s.exist(board, "ABCB"));
System.out.println(s.exist(grid("A"), "A"));
System.out.println(s.exist(grid("A"), "AB"));
}
}true
true
false
true
falseTime: O(m · n · 3^L · L) where L is the word length: after the first letter each step has at most 3 new directions, and the path check costs up to L. Space: O(L).
Optimal: mark cells in place, prune early
Both versions explore the same tree, so the worst case stays O(m · n · 3^L); the second removes the overhead and skips hopeless searches:
- Mark in place. Overwrite the current cell with a sentinel (
'#') while exploring below it and restore it afterwards. The "already used" test becomes a plain character comparison,O(1), with no path list. The board is the caller's array, so the method changes it temporarily and every path out ofdfsrestores it. - Cheap rejections up front. If the word is longer than the board has cells, or the board has too few of some letter, the answer is
falsewithout any search. The letter counts use anint[128]indexed by character code, which covers the ASCII letters in the constraints. - Search from the rarer end. If the first letter of the word is more common on the board than the last, reverse the word. Fewer starting cells means fewer DFS roots, and reversing the word does not change whether a path exists.
public class Main {
static class Solution {
public boolean exist(char[][] board, String word) {
int rows = board.length;
int cols = board[0].length;
if (word.length() > rows * cols) {
return false;
}
int[] counts = new int[128];
for (char[] row : board) {
for (char ch : row) {
counts[ch]++;
}
}
int[] needed = new int[128];
for (char ch : word.toCharArray()) {
needed[ch]++;
}
for (int ch = 0; ch < 128; ch++) {
if (counts[ch] < needed[ch]) {
return false;
}
}
char[] w = word.toCharArray();
if (counts[w[0]] > counts[w[w.length - 1]]) {
reverse(w);
}
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (dfs(board, w, 0, r, c)) {
return true;
}
}
}
return false;
}
private void reverse(char[] w) {
for (int i = 0, j = w.length - 1; i < j; i++, j--) {
char t = w[i];
w[i] = w[j];
w[j] = t;
}
}
private boolean dfs(char[][] board, char[] word, int idx, int r, int c) {
if (board[r][c] != word[idx]) {
return false;
}
if (idx + 1 == word.length) {
return true;
}
char saved = board[r][c];
board[r][c] = '#'; // mark as used
int rows = board.length;
int cols = board[0].length;
boolean found = (r > 0 && dfs(board, word, idx + 1, r - 1, c))
|| (r + 1 < rows && dfs(board, word, idx + 1, r + 1, c))
|| (c > 0 && dfs(board, word, idx + 1, r, c - 1))
|| (c + 1 < cols && dfs(board, word, idx + 1, r, c + 1));
board[r][c] = saved; // undo
return found;
}
}
static char[][] grid(String... rows) {
char[][] g = new char[rows.length][];
for (int i = 0; i < rows.length; i++) {
g[i] = rows[i].toCharArray();
}
return g;
}
public static void main(String[] args) {
Solution s = new Solution();
char[][] board = grid("ABCE", "SFCS", "ADEE");
System.out.println(s.exist(board, "ABCCED"));
System.out.println(s.exist(board, "SEE"));
System.out.println(s.exist(board, "ABCB"));
System.out.println(s.exist(grid("A"), "A"));
System.out.println(s.exist(grid("A"), "AB"));
}
}true
true
false
true
falseTime: O(m · n · 3^L) worst case. Space: O(L) recursion depth; the board is mutated in place and restored. The bounds checks use r > 0 and r + 1 < rows before each recursive call, so no index is ever outside the board.