SyntaxPilot
Courses/DSA and Coding Problems/Lesson 35
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

DSA and Coding Problems · Lesson 35 of 90

Word search in a grid

queued

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)?

  1. i == w.length(): every letter matched → true.
  2. Off the grid, or g[r][c] != w.charAt(i) → false immediately (pruning).
  3. 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

  1. 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).

  1. 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).

  1. 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);
    }
  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"));
  • true
  • false
  • ArrayIndexOutOfBoundsException
  • 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

  1. 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.
  2. How do you avoid reusing a square without extra memory? Overwrite it with a marker like '#' and restore it after the recursive calls.
  3. Why must the bounds check come first? || evaluates left to right; reading g[-1] would throw before the bounds test ran.
  4. Time complexity? O(m·n · 3^L); space O(L) for the recursion.
  5. 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.
  6. 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 L and 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 in f first).
  • O(m·n · 3^L) worst case, O(L) space, and milliseconds on real grids.

Next episode: Trees: preorder, inorder, postorder and level order.