Word Search II

HARD✓ CHIP-TIMEDLC #212 — FULL STATEMENT ↗

The drill: A letter grid and a list of candidate words — report every candidate that can actually be traced out by stepping to horizontally or vertically adjacent cells, never reusing a cell inside the same word.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

A letter grid and a list of candidate words arrive together. For each candidate, the question is whether it can be traced by stepping to horizontally or vertically adjacent cells, one letter per step, never reusing a cell within that word's own path.

The output is the list of candidates that actually succeed — every word that can't be traced on the board is simply left out, and a word that appears twice in the candidate list should still only be reported once.

Different candidate words may reuse the very same cells on the board; the no-reuse rule only applies within a single word's own path, not across separate words.

EX 01

board = ["race", "oats", "ring", "edym"] · words = ["race", "oats", "ring", "rore", "cast", "zzz"]

→ ["race", "oats", "ring", "rore"]

STRAIGHT HORIZONTAL AND VERTICAL PATHS ON A 4X4 GRID, TWO CANDIDATES ABSENT

EX 02

board = ["x"] · words = ["x", "y"]

→ ["x"]

SINGLE-CELL BOARD

EX 03

board = ["ab", "cd"] · words = ["abdc", "abc"]

→ ["abdc"]

A WORD USING EVERY CELL EXACTLY ONCE VIA A TURN, VERSUS ONE THAT CAN'T BE FORMED AT ALL

grids stay modest, typically a few hundred cells
candidate words are generally short, well under twenty letters each
a single word's path never reuses the same cell twice
each qualifying candidate is reported once, even if listed multiple times

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

Running the single-word board search once per candidate re-walks the same grid from scratch every time — most of that work retraces paths that no candidate even starts with. What if every candidate's search could share its early steps?

HINT 2 THE STRUCTURE

Words with the same prefix should share the same walk down the board until they actually diverge — that's exactly the shape a trie stores, letter by letter.

HINT 3 ONE STEP FROM THE ANSWER

Merge all the candidate words into one trie first, then do a single backtracking scan of the board following trie edges instead of blind neighbors. Whenever the node you land on is marked as a complete word, record it and clear that mark so it's never recorded twice.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE MERGED WALKPATTERN · TRIE-GUIDED BACKTRACKINGboard = ["an","xt"] · words = [an, ant, at]

STEP 1

Words an, ant, at merge into one trie: a branches to n (word 'an', continuing to t for 'ant') and to t (word 'at').

STEP 1 / 8 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/word-search-ii.py — RACE PACE

LANG ▸

PACE ▸

class TrieNode:
    def __init__(self):
        self.children = {}
        self.word = None  # the full word, set only at a terminal node


class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        root = TrieNode()
        for w in words:
            node = root
            for ch in w:
                node = node.children.setdefault(ch, TrieNode())
            node.word = w

        rows, cols = len(board), len(board[0])
        result = []

        def dfs(r: int, c: int, node: TrieNode) -> None:
            ch = board[r][c]
            child = node.children.get(ch)
            if child is None:
                return
            if child.word is not None:
                result.append(child.word)
                child.word = None  # never report the same word twice

            board[r][c] = "#"
            for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols and board[nr][nc] != "#":
                    dfs(nr, nc, child)
            board[r][c] = ch

            if not child.children:
                del node.children[ch]  # dead branch, prune it for later scans

        for r in range(rows):
            for c in range(cols):
                dfs(r, c, root)

        return result

TIME O(M·N·4^L)SPACE O(Σ|WORDS|)PYTHON · RACE PACE · 42 LN

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

        def exists(word: str) -> bool:
            def dfs(r: int, c: int, i: int) -> bool:
                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
                tmp = board[r][c]
                board[r][c] = "#"
                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] = tmp
                return found

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

        return [w for w in words if exists(w)]

TIME O(W·M·N·4^L)SPACE O(L)PYTHON · TRAINING PACE · 28 LN

class WsTrieNode {
    Map<Character, WsTrieNode> children = new HashMap<>();
    String word = null; // the full word, set only at a terminal node
}

class Solution {
    private char[][] board;
    private int rows, cols;
    private List<String> result;

    public List<String> findWords(char[][] board, String[] words) {
        WsTrieNode root = new WsTrieNode();
        for (String w : words) {
            WsTrieNode node = root;
            for (char c : w.toCharArray()) {
                node = node.children.computeIfAbsent(c, k -> new WsTrieNode());
            }
            node.word = w;
        }

        this.board = board;
        this.rows = board.length;
        this.cols = board[0].length;
        this.result = new ArrayList<>();

        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                dfs(r, c, root);
            }
        }
        return result;
    }

    private void dfs(int r, int c, WsTrieNode node) {
        char ch = board[r][c];
        WsTrieNode child = node.children.get(ch);
        if (child == null) {
            return;
        }
        if (child.word != null) {
            result.add(child.word);
            child.word = null; // never report the same word twice
        }

        board[r][c] = '#';
        int[][] dirs = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
        for (int[] d : dirs) {
            int nr = r + d[0], nc = c + d[1];
            if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && board[nr][nc] != '#') {
                dfs(nr, nc, child);
            }
        }
        board[r][c] = ch;

        if (child.children.isEmpty()) {
            node.children.remove(ch); // dead branch, prune it for later scans
        }
    }
}

TIME O(M·N·4^L)SPACE O(Σ|WORDS|)JAVA · RACE PACE · 59 LN

class Solution {
    private char[][] board;
    private int rows, cols;

    public List<String> findWords(char[][] board, String[] words) {
        this.board = board;
        this.rows = board.length;
        this.cols = board[0].length;

        List<String> result = new ArrayList<>();
        for (String w : words) {
            if (exists(w)) {
                result.add(w);
            }
        }
        return result;
    }

    private boolean exists(String word) {
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (dfs(r, c, word, 0)) {
                    return true;
                }
            }
        }
        return false;
    }

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

TIME O(W·M·N·4^L)SPACE O(L)JAVA · TRAINING PACE · 46 LN

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