Word Search

MEDIUM✓ CHIP-TIMEDLC #79 — FULL STATEMENT ↗

The drill: Starting from any cell, snake through a grid to neighbouring cells (up, down, left, right), spelling out a word one letter per cell without reusing a cell in the same path — determine whether the word can be traced this way.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

A grid of letters and a target word arrive together. Starting from any single cell, the drill is to snake through the grid — one step at a time to a cell directly above, below, left, or right — spelling the word out letter by letter.

A path may never step onto the same cell twice while tracing one attempt, though a cell can be revisited by a different attempt starting elsewhere. The only question to answer is whether some starting cell and some path spells the whole word.

Diagonal moves don't count as adjacency, and the word must be spelled in full — a path that matches only a prefix or stalls partway through doesn't count as a success.

EX 01

board = ["CAT", "AAT", "TTT"] · word = "CAT"

→ true

STRAIGHT PATH DOWN THE FIRST COLUMN

EX 02

board = ["CAT", "AAT", "TTT"] · word = "CATTT"

→ true

LONGER PATH WINDING THROUGH DISTINCT T CELLS

EX 03

board = ["CAT", "AAT", "TTT"] · word = "CATS"

→ false

LETTER S DOESN'T EXIST ANYWHERE IN THE BOARD

grids stay modest, typically no more than a few hundred cells
the word length is generally under twenty characters
a single path may never reuse the same cell twice
only up/down/left/right moves count as adjacent

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

The word can start anywhere, so a full solution has to try every cell as a starting point — and once inside a path, a cell already stepped on can't be revisited in that same attempt.

HINT 2 THE STRUCTURE

Marking 'visited' doesn't need a separate structure — the grid itself is free to write into. Overwrite a cell you step on with a character the word can never contain, then put the original letter back before trying a different direction.

HINT 3 ONE STEP FROM THE ANSWER

DFS from a starting cell: if the current cell matches the current letter, temporarily blank it, recurse into all four neighbours for the next letter, then restore it. Success is reaching one past the last letter.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE IN-PLACE SNAKEPATTERN · DFS, MARK IN PLACEboard = ["CAT","AAT","TTT"] · word = "CAT"

STEP 1

Word CAT on a 3x3 board. Try every starting cell — begin at row 0, column 0, which holds 'C'.

STEP 1 / 6 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/word-search.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        rows, cols = len(board), len(board[0])

        def dfs(r, c, i):
            if i == len(word):
                return True
            if r < 0 or r >= rows or c < 0 or c >= cols or board[r][c] != word[i]:
                return False
            temp = board[r][c]
            board[r][c] = "#"  # blank it in place — the grid IS the visited set
            found = (
                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)
            )
            board[r][c] = temp
            return found

        for r in range(rows):
            for c in range(cols):
                if dfs(r, c, 0):
                    return True
        return False

TIME O(M·N·4ᴸ)SPACE O(L)PYTHON · RACE PACE · 25 LN

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        rows, cols = len(board), len(board[0])

        def dfs(r, c, i, visited):
            if i == len(word):
                return True
            if r < 0 or r >= rows or c < 0 or c >= cols:
                return False
            if (r, c) in visited or board[r][c] != word[i]:
                return False
            visited.add((r, c))
            found = (
                dfs(r + 1, c, i + 1, visited)
                or dfs(r - 1, c, i + 1, visited)
                or dfs(r, c + 1, i + 1, visited)
                or dfs(r, c - 1, i + 1, visited)
            )
            visited.remove((r, c))
            return found

        for r in range(rows):
            for c in range(cols):
                if dfs(r, c, 0, set()):
                    return True
        return False

TIME O(M·N·4ᴸ)SPACE O(L)PYTHON · TRAINING PACE · 26 LN

class Solution {
    public boolean exist(char[][] board, String word) {
        int rows = board.length, cols = board[0].length;
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (dfs(board, word, r, c, 0)) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean dfs(char[][] board, String word, int r, int c, int i) {
        if (i == word.length()) {
            return true;
        }
        int rows = board.length, cols = board[0].length;
        if (r < 0 || r >= rows || c < 0 || c >= cols || board[r][c] != word.charAt(i)) {
            return false;
        }
        char temp = board[r][c];
        board[r][c] = '#';
        boolean found = dfs(board, word, r + 1, c, i + 1)
                || dfs(board, word, r - 1, c, i + 1)
                || dfs(board, word, r, c + 1, i + 1)
                || dfs(board, word, r, c - 1, i + 1);
        board[r][c] = temp;
        return found;
    }
}

TIME O(M·N·4ᴸ)SPACE O(L)JAVA · RACE PACE · 31 LN

class Solution {
    public boolean exist(char[][] board, String word) {
        int rows = board.length, cols = board[0].length;
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (dfs(board, word, r, c, 0, new HashSet<>())) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean dfs(char[][] board, String word, int r, int c, int i, Set<Integer> visited) {
        if (i == word.length()) {
            return true;
        }
        int rows = board.length, cols = board[0].length;
        if (r < 0 || r >= rows || c < 0 || c >= cols) {
            return false;
        }
        int key = r * cols + c;
        if (visited.contains(key) || board[r][c] != word.charAt(i)) {
            return false;
        }
        visited.add(key);
        boolean found = dfs(board, word, r + 1, c, i + 1, visited)
                || dfs(board, word, r - 1, c, i + 1, visited)
                || dfs(board, word, r, c + 1, i + 1, visited)
                || dfs(board, word, r, c - 1, i + 1, visited);
        visited.remove(key);
        return found;
    }
}

TIME O(M·N·4ᴸ)SPACE O(L)JAVA · TRAINING PACE · 34 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED