These are the notes for DSA episode 35, LeetCode 79. Given a grid of letters and a word, decide whether the word can be traced through neighbouring squares (up, down, left, right), using each square at most once. The obvious way walks every path of the word's length from every square and compares the letters only at the end: correct on the examples, but a 21-letter phrase on an 8 x 8 grid takes about 70 seconds. The fix is grid DFS with pruning: compare one letter per step and stop at the first wrong letter, and mark a square as used by overwriting it with '#', restoring it on the way back. Every program below was run in the SyntaxPilot compiler (8-second time limit), and the outputs shown are real.
The problem, in real life
On the back of a snack packet there's a word hunt: a grid of letters. Find the word SAMOSA: start on an S, step to a neighbouring A, then an M, and so on. Each step goes up, down, left or right: no diagonal jumps, so the word can bend and snake around the grid. And you can't step on the same square twice in one word.
| On the snack packet | In the code |
|---|---|
| The grid of letters | char[][] g (m rows, n columns) |
| The word to find | String w |
| "I'm on this square" | (r, c) |
| "I need the i-th letter next" | index i into w |
| A step up / down / left / right | (r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1) |
| Pencil mark on a used square | g[r][c] = '#' |
Problem statement
Word Search (LeetCode 79). Given an m x n grid of characters board and a string word, return true if word exists in the grid. The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighbouring. The same letter cell may not be used more than once.
A B C E
S F C S
A D E E
"ABCCED" → true "SEE" → true "ABCB" → false
ABCB is false because the only B next to the C is the one already used. Edge cases: a 1 x 1 grid, a word that uses every square (ABCESEEDASFC: true), a word longer than the grid (ABCESEEDASFCX: false).
Brute force: walk every path, compare at the end
From every square, walk in all four directions (never onto a square already on this path, tracked in seen), collect the letters into path, and when path is as long as the word, compare.
import java.util.*;
public class Main {
static boolean brute(char[][] g, int r, int c, String path, String w,
boolean[][] seen) {
if (r < 0 || c < 0 || r >= g.length || c >= g[0].length || seen[r][c])
return false;
path = path + g[r][c];
if (path.length() == w.length()) return path.equals(w);
seen[r][c] = true;
boolean f = brute(g, r + 1, c, path, w, seen) || brute(g, r - 1, c, path, w, seen)
|| brute(g, r, c + 1, path, w, seen) || brute(g, r, c - 1, path, w, seen);
seen[r][c] = false;
return f;
}
static boolean bruteExist(char[][] g, String w) {
for (int r = 0; r < g.length; r++)
for (int c = 0; c < g[0].length; c++)
if (brute(g, r, c, "", w, new boolean[g.length][g[0].length]))
return true;
return false;
}
public static void main(String[] args) {
char[][] g = {"ABCE".toCharArray(),
"SFCS".toCharArray(),
"ADEE".toCharArray()};
System.out.println(bruteExist(g, "ABCCED"));
System.out.println(bruteExist(g, "SEE"));
System.out.println(bruteExist(g, "ABCB"));
}
}
Real output: true, true, false. Correct.
Now an 8 x 8 grid of snack names and a 21-letter phrase that is not in it:
import java.util.*;
public class Main {
static boolean brute(char[][] g, int r, int c, String path, String w,
boolean[][] seen) {
if (r < 0 || c < 0 || r >= g.length || c >= g[0].length || seen[r][c])
return false;
path = path + g[r][c];
if (path.length() == w.length()) return path.equals(w);
seen[r][c] = true;
boolean f = brute(g, r + 1, c, path, w, seen) || brute(g, r - 1, c, path, w, seen)
|| brute(g, r, c + 1, path, w, seen) || brute(g, r, c - 1, path, w, seen);
seen[r][c] = false;
return f;
}
static boolean bruteExist(char[][] g, String w) {
for (int r = 0; r < g.length; r++)
for (int c = 0; c < g[0].length; c++)
if (brute(g, r, c, "", w, new boolean[g.length][g[0].length]))
return true;
return false;
}
public static void main(String[] args) {
String[] rows = {"CHAIPAKO", "SAMOSARA", "JALEBIPA", "PAKORADO",
"LASSIKUL", "KULFISAM", "BHELPURI", "DOSAIDLI"};
char[][] h = new char[8][];
for (int i = 0; i < 8; i++) h[i] = rows[i].toCharArray();
String w = "JALEBIANDSAMOSAPLEASE";
long t0 = System.nanoTime();
System.out.println(bruteExist(h, w));
System.out.println((System.nanoTime() - t0) / 1000000 + " ms");
}
}
Real result: Time Limit Exceeded.
Why the brute force fails
| Word length (8 x 8 grid, word absent) | Brute force time |
|---|---|
| 16 letters | 2.4 s |
| 18 letters | 8 s |
| 21 letters | about 70 s |
The phrase starts with J, and only one square of the grid is a J. But the brute force starts at every square, even a C or an S, and walks 21 steps from it before comparing anything. From one square there can be up to 4 · 3^20 paths (each step after the first has at most 3 new directions), and every step copies the path string. The question: can we stop the moment one letter is wrong?
The key insight: compare one letter per step
Carry an index i instead of a path string. dfs(r, c, i) answers: does the rest of the word, from letter i, start at square (r, c)?
i == w.length(): every letter matched →true.- Off the grid, or
g[r][c] != w.charAt(i)→falseimmediately (pruning). - Otherwise mark the square, try the four neighbours with
i + 1, restore the square.
DFS (depth-first search) means: go as deep as you can down one path, then back up and try the next.
Marking without a seen grid: overwrite the square with '#' while it is on the current path. '#' never equals a letter of the word, so the square can't be reused. On the way back, put the letter back.
The search for ABCCED, step by step
| Need | At | Neighbours tried (down, up, right, left) |
|---|---|---|
A (i = 0) |
(0,0) = A ✓, mark # |
down (1,0) = S ✗, up off the grid ✗, right (0,1) = B ✓ |
C (i = 2) |
at B (0,1) |
down (1,1) = F ✗, right (0,2) = C ✓ |
C, E |
(1,2) = C, (2,2) = E |
|
D (i = 5) |
at E (2,2) |
up (1,2) = # ✗ (used), right (2,3) = E ✗, left (2,1) = D ✓ |
| — (i = 6) | i == 6: true; every # is put back on the way up |
For ABCB: after A, B, C at (0,2), the B to its left is a #, down is C, right is E: false.
The optimal solution in Java
import java.util.*;
public class Main {
static boolean dfs(char[][] g, int r, int c, String w, int i) {
if (i == w.length()) return true;
if (r < 0 || c < 0 || r >= g.length || c >= g[0].length
|| g[r][c] != w.charAt(i)) return false;
char t = g[r][c];
g[r][c] = '#';
boolean f = dfs(g, r + 1, c, w, i + 1) || dfs(g, r - 1, c, w, i + 1)
|| dfs(g, r, c + 1, w, i + 1) || dfs(g, r, c - 1, w, i + 1);
g[r][c] = t;
return f;
}
static boolean exist(char[][] g, String w) {
for (int r = 0; r < g.length; r++)
for (int c = 0; c < g[0].length; c++)
if (dfs(g, r, c, w, 0)) return true;
return false;
}
public static void main(String[] args) {
char[][] g = {"ABCE".toCharArray(),
"SFCS".toCharArray(),
"ADEE".toCharArray()};
System.out.println(exist(g, "ABCCED"));
System.out.println(exist(g, "SEE"));
System.out.println(exist(g, "ABCB"));
System.out.println(exist(new char[][]{{'A'}}, "A"));
System.out.println(exist(g, "ABCESEEDASFC"));
System.out.println(exist(g, "ABCESEEDASFCX"));
}
}
Real output:
true
true
false
true
true
false
The snack grid that timed out:
import java.util.*;
public class Main {
static boolean dfs(char[][] g, int r, int c, String w, int i) {
if (i == w.length()) return true;
if (r < 0 || c < 0 || r >= g.length || c >= g[0].length
|| g[r][c] != w.charAt(i)) return false;
char t = g[r][c];
g[r][c] = '#';
boolean f = dfs(g, r + 1, c, w, i + 1) || dfs(g, r - 1, c, w, i + 1)
|| dfs(g, r, c + 1, w, i + 1) || dfs(g, r, c - 1, w, i + 1);
g[r][c] = t;
return f;
}
static boolean exist(char[][] g, String w) {
for (int r = 0; r < g.length; r++)
for (int c = 0; c < g[0].length; c++)
if (dfs(g, r, c, w, 0)) return true;
return false;
}
public static void main(String[] args) {
String[] rows = {"CHAIPAKO", "SAMOSARA", "JALEBIPA", "PAKORADO",
"LASSIKUL", "KULFISAM", "BHELPURI", "DOSAIDLI"};
char[][] h = new char[8][];
for (int i = 0; i < 8; i++) h[i] = rows[i].toCharArray();
String w = "JALEBIANDSAMOSAPLEASE";
long t0 = System.nanoTime();
System.out.println(exist(h, w) + ", " + exist(h, "SAMOSA") + ", " + exist(h, "JALEBI"));
System.out.println((System.nanoTime() - t0) / 1000000 + " ms");
}
}
Real output: false, true, true and a few milliseconds. Most starting squares are rejected after a single comparison.
Note the bounds check comes before reading g[r][c]: with ||, Java evaluates left to right and stops at the first true, so an off-grid square is never read.
The same solution in C++
#include <bits/stdc++.h>
using namespace std;
bool dfs(vector<string>& g, int r, int c, const string& w, int i) {
if (i == (int)w.size()) return true;
if (r < 0 || c < 0 || r >= (int)g.size() || c >= (int)g[0].size()
|| g[r][c] != w[i]) return false;
char t = g[r][c];
g[r][c] = '#';
bool f = dfs(g, r + 1, c, w, i + 1) || dfs(g, r - 1, c, w, i + 1)
|| dfs(g, r, c + 1, w, i + 1) || dfs(g, r, c - 1, w, i + 1);
g[r][c] = t;
return f;
}
bool exist(vector<string>& g, const string& w) {
for (int r = 0; r < (int)g.size(); r++)
for (int c = 0; c < (int)g[0].size(); c++)
if (dfs(g, r, c, w, 0)) return true;
return false;
}
int main() {
vector<string> g = {"ABCE", "SFCS", "ADEE"};
cout << boolalpha;
for (string w : {"ABCCED", "SEE", "ABCB", "ABCESEEDASFC", "ABCESEEDASFCX"})
cout << w << ": " << exist(g, w) << '\n';
}
Output: ABCCED: true, SEE: true, ABCB: false, ABCESEEDASFC: true, ABCESEEDASFCX: false.
The same solution in Python
def exist(g, w):
m, n = len(g), len(g[0])
def dfs(r, c, i):
if i == len(w):
return True
if r < 0 or c < 0 or r >= m or c >= n or g[r][c] != w[i]:
return False
t, g[r][c] = g[r][c], "#"
f = 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)
g[r][c] = t
return f
return any(dfs(r, c, 0) for r in range(m) for c in range(n))
g = [list("ABCE"), list("SFCS"), list("ADEE")]
for w in ["ABCCED", "SEE", "ABCB", "ABCESEEDASFC", "ABCESEEDASFCX"]:
print(w + ":", exist(g, w))
Output: the same five lines, with True/False.
Three real bugs
Bug 1: no visited mark
import java.util.*;
public class Main {
static boolean dfs(char[][] g, int r, int c, String w, int i) {
if (i == w.length()) return true;
if (r < 0 || c < 0 || r >= g.length || c >= g[0].length
|| g[r][c] != w.charAt(i)) return false;
char t = g[r][c];
boolean f = dfs(g, r + 1, c, w, i + 1) || dfs(g, r - 1, c, w, i + 1)
|| dfs(g, r, c + 1, w, i + 1) || dfs(g, r, c - 1, w, i + 1);
return f;
}
static boolean exist(char[][] g, String w) {
for (int r = 0; r < g.length; r++)
for (int c = 0; c < g[0].length; c++)
if (dfs(g, r, c, w, 0)) return true;
return false;
}
public static void main(String[] args) {
char[][] g = {"ABCE".toCharArray(),
"SFCS".toCharArray(),
"ADEE".toCharArray()};
System.out.println(exist(g, "ABCB"));
System.out.println(exist(g, "ABA"));
}
}
Real output: true and true. Without the #, the search steps from B straight back onto the B (or the A) it came from.
Bug 2: reading the square before the bounds check
import java.util.*;
public class Main {
static boolean dfs(char[][] g, int r, int c, String w, int i) {
if (i == w.length()) return true;
if (g[r][c] != w.charAt(i) || r < 0 || c < 0
|| r >= g.length || c >= g[0].length) return false;
char t = g[r][c];
g[r][c] = '#';
boolean f = dfs(g, r + 1, c, w, i + 1) || dfs(g, r - 1, c, w, i + 1)
|| dfs(g, r, c + 1, w, i + 1) || dfs(g, r, c - 1, w, i + 1);
g[r][c] = t;
return f;
}
static boolean exist(char[][] g, String w) {
for (int r = 0; r < g.length; r++)
for (int c = 0; c < g[0].length; c++)
if (dfs(g, r, c, w, 0)) return true;
return false;
}
public static void main(String[] args) {
char[][] g = {"ABCE".toCharArray(),
"SFCS".toCharArray(),
"ADEE".toCharArray()};
System.out.println(exist(g, "ABCCED"));
}
}
Real output:
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index -1 out of bounds for length 3
at Main.dfs(Main.java:6)
The search tried to step up from row 0 to row -1 and read it before checking that it exists.
Bug 3: never putting the letter back
import java.util.*;
public class Main {
static boolean dfs(char[][] g, int r, int c, String w, int i) {
if (i == w.length()) return true;
if (r < 0 || c < 0 || r >= g.length || c >= g[0].length
|| g[r][c] != w.charAt(i)) return false;
char t = g[r][c];
g[r][c] = '#';
boolean f = dfs(g, r + 1, c, w, i + 1) || dfs(g, r - 1, c, w, i + 1)
|| dfs(g, r, c + 1, w, i + 1) || dfs(g, r, c - 1, w, i + 1);
return f;
}
static boolean exist(char[][] g, String w) {
for (int r = 0; r < g.length; r++)
for (int c = 0; c < g[0].length; c++)
if (dfs(g, r, c, w, 0)) return true;
return false;
}
public static void main(String[] args) {
char[][] g = {"ABCE".toCharArray(),
"SFCS".toCharArray(),
"ADEE".toCharArray()};
System.out.println(exist(g, "ABCB"));
System.out.println(exist(g, "ABCCED"));
for (char[] row : g) System.out.println(new String(row));
}
}
Real output:
false
false
###E
SFCS
#DEE
ABCB is correctly false, but its failed search left # signs behind, so ABCCED is now false too.
Complexity
Let the grid be m x n and the word have L letters.
| Approach | Time | Extra space | 21 letters, 8 x 8 |
|---|---|---|---|
| Walk every path, compare at the end | O(m·n · 4·3^(L-1) · L) | O(m·n) seen + O(L) |
~70 s, TLE |
| DFS + compare per step | O(m·n · 3^L) worst case | O(L) recursion, no extra grid | milliseconds |
Why 3^L: after the first step, one of the four neighbours is the square we came from (it's a #), so at most 3 new directions remain. The worst case is a grid where almost every letter matches, e.g. all As and the word AAAA...AB. On ordinary grids the first wrong letter ends almost every path.
Common mistakes
| Mistake | What you see | Why | Fix |
|---|---|---|---|
| No visited mark | ABCB → true, ABA → true |
squares reused | g[r][c] = '#' while on the path |
| Letter compared before the bounds | ArrayIndexOutOfBoundsException: Index -1 out of bounds for length 3 |
an off-grid square is read | bounds first, then the letter |
| Letter never restored | ABCCED → false; grid ###E / SFCS / #DEE |
a failed search wrecks the grid | g[r][c] = t after the calls |
return true before the restore line |
grid keeps # after a success |
the letter is never put back | store the result in f, restore, return f |
| Allowing diagonal moves by accident | true for words that need a diagonal | 8 directions instead of 4 | exactly four calls |
Building a path string |
slow | a new string every step | compare one character with index i |
Mini project: the snack-packet puzzle maker
Write a program that takes a grid and a list of words, and prints each word with FOUND and its starting square, or NOT FOUND. Extension: also print the path, e.g. SAMOSA: (1,0) (1,1) (1,2) (1,3) (1,4) (1,5). (Hint: push (r, c) onto a list when you mark a square, remove it when you restore.)
Practice
- Count the paths. How many different ways can the word be traced? (Don't stop at the first.)
Solution
Return an int: at i == w.length() return 1; otherwise add up the four recursive counts (no short-circuit), restore the letter, and return the sum. Add up count(r, c, 0) over all starting squares.
static int count(char[][] g, int r, int c, String w, int i) {
if (i == w.length()) return 1;
if (r < 0 || c < 0 || r >= g.length || c >= g[0].length || g[r][c] != w.charAt(i)) return 0;
char t = g[r][c];
g[r][c] = '#';
int k = count(g, r + 1, c, w, i + 1) + count(g, r - 1, c, w, i + 1)
+ count(g, r, c + 1, w, i + 1) + count(g, r, c - 1, w, i + 1);
g[r][c] = t;
return k;
}
In the example grid, SEE can be traced in exactly 1 way: S (1,3) → E (2,3) → E (2,2).
- Eight directions. Allow diagonal steps too.
Solution
Loop over int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1},{1,1},{1,-1},{-1,1},{-1,-1}} and call dfs(g, r + d[0], c + d[1], w, i + 1), stopping at the first true. The time becomes O(m·n · 7^L).
- Number of Islands (LeetCode 200): count the groups of
'1's connected up/down/left/right.
Solution
The same four-direction DFS without a word: for every '1', add one island and "sink" the whole group by overwriting each visited '1' with '0' (no restore needed, because each square should be counted once).
static void sink(char[][] g, int r, int c) {
if (r < 0 || c < 0 || r >= g.length || c >= g[0].length || g[r][c] != '1') return;
g[r][c] = '0';
sink(g, r + 1, c); sink(g, r - 1, c); sink(g, r, c + 1); sink(g, r, c - 1);
}
- Word Search II (LeetCode 212): find all of many words at once.
Solution
Running word search once per word is too slow for thousands of words. Put all the words in a trie (a tree of letters) and walk the grid once, following the trie as you step; prune when no word starts with the current prefix. Tries come later in the course.
Quick quiz
// g = ABCE / SFCS / ADEE
System.out.println(exist(g, "SFCSE"));
truefalseArrayIndexOutOfBoundsException- the grid with
#in it
Answer
true. S (1,0) → F (1,1) → C (1,2) → S (1,3) → E (2,3): five different neighbouring squares. The grid is restored afterwards.
Interview questions
- Why DFS and not BFS here? We follow one path at a time and need to un-use squares when we back up; recursion makes that natural.
- How do you avoid reusing a square without extra memory? Overwrite it with a marker like
'#'and restore it after the recursive calls. - Why must the bounds check come first?
||evaluates left to right; readingg[-1]would throw before the bounds test ran. - Time complexity? O(m·n · 3^L); space O(L) for the recursion.
- What is the worst-case input? A grid of one repeated letter and a word of that letter ending in a letter that isn't there.
- Can you prune more? Check letter counts first (if the grid has fewer
Ss than the word, return false), and search from whichever end of the word has the rarer first letter.
Glossary
| Term | Meaning |
|---|---|
| Grid / matrix | A 2D array of rows and columns |
| Adjacent / neighbour | The square directly up, down, left or right |
| DFS (depth-first search) | Follow one path as deep as possible, then back up and try another |
| Backtracking | Undo a choice (here: restore the letter) when backing up |
| Pruning | Stopping a path as soon as it can't succeed (a wrong letter) |
| Visited marker | A value like '#' written into a square so it isn't reused |
Short-circuit \|\| |
Java stops evaluating a \|\| b as soon as a is true |
| Bounds check | Making sure 0 ≤ r < m and 0 ≤ c < n before reading g[r][c] |
| Trie | A tree of letters used to store many words by their prefixes |
| Time Limit Exceeded (TLE) | Too slow for the judge's limit (8 s in the SyntaxPilot compiler) |
Summary
- Walking every path of length
Land comparing at the end: 16 letters 2.4 s, 21 letters ~70 s. - Compare one letter per step and stop at the first mismatch; check the bounds before reading the grid.
- Mark used squares with
'#'and restore them after the four calls (save the result inffirst). - O(m·n · 3^L) worst case, O(L) space, and milliseconds on real grids.
Next episode: Trees: preorder, inorder, postorder and level order.