A packing floor had one letter stenciled on every tile so night-shift trainers could walk a product name: step to a neighbor, never a diagonal, never the same tile twice in one walk. The first job treated each catalog name as its own grid search. A dozen names on a 3×4 fixture returned before coffee. Thirty thousand names on the live floor were still searching when the request timed out.

Word Search II asks which dictionary words can be walked on a letter grid. This is an interview writeup, not a layout lecture. The trie post owns the node; the graph post owns a grid as a 4-direction graph; backtracking owns choose, recurse, and undo. Here we only care about inserting the dictionary, then walking from each cell while the prefix still exists.

The problem

Given a char[][] board of lowercase letters and a String[] words dictionary, return every word that can be formed by a walk on the board. A walk steps to an up, down, left, or right neighbor — not a diagonal — and may not reuse a cell in one word. Order of the answer does not matter.

board =
w a r e
h o u s
e l p t

words = ["ware", "house", "help", "war", "our", "whole", "plus", "hot"]

→  ["ware", "house", "help", "war", "our", "whole"]

ware is the first row. house walks the second row and then up into the e of ware. plus dies: after p → l, the u is a diagonal. hot dies: t is not a 4-neighbor of o.

Note: Two words may share tiles. That is why you unmark the cell when the walk returns — the next start still needs it. Reusing a cell inside one word is the bug the mark prevents.

A search per word is the honest brute force

Run Word Search once per dictionary name — one 4-direction DFS per word, mark and unmark as you go. Or generate every path of every length from every cell and probe a HashSet of the names. Both are correct. Both ignore that a dead prefix kills every longer candidate at once.

The Java below is the path generator. maxLen is the longest dictionary word, so a 12-cell snake is not a gift.

List<String> findWordsEveryPath(char[][] board, String[] words) {
    Set<String> dict = new HashSet<>();
    int maxLen = 0;
    for (String w : words) {
        dict.add(w);
        maxLen = Math.max(maxLen, w.length());
    }
    Set<String> found = new HashSet<>();
    int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    StringBuilder path = new StringBuilder();
    for (int r = 0; r < board.length; r++) {
        for (int c = 0; c < board[0].length; c++) {
            collect(board, r, c, path, dict, found, dirs, maxLen);
        }
    }
    return new ArrayList<>(found);
}

void collect(char[][] board, int r, int c, StringBuilder path,
             Set<String> dict, Set<String> found, int[][] dirs, int maxLen) {
    if (r < 0 || r >= board.length || c < 0 || c >= board[0].length) {
        return;
    }
    char ch = board[r][c];
    if (ch == '#') {
        return;
    }
    path.append(ch);
    board[r][c] = '#';
    if (dict.contains(path.toString())) {
        found.add(path.toString());
    }
    if (path.length() < maxLen) {
        for (int[] d : dirs) {
            collect(board, r + d[0], c + d[1], path, dict, found, dirs, maxLen);
        }
    }
    board[r][c] = ch;
    path.deleteCharAt(path.length() - 1);
}

At a 3×4 fixture this is a rounding error. On a live board with tens of thousands of names you still generate walks that match nothing: does this cell still extend a live prefix?

Insert the dictionary, then DFS while the prefix lives

Insert every word with the same Implement Trie walk: create missing a–z edges, set endOfWord on the last node. We also store the full string on that end node so a hit copies into the answer without rebuilding the path.

From each board cell, DFS four neighbors while the next letter still has a child — a missing child is a wall — and record when endOfWord is true. Mark the cell before the recursive calls, unmark after — choose, recurse, undo. Add and Search Words DFS-es trie children because . matches any letter; here the next character comes from a neighbor cell, and you step the trie only if that letter has an edge.

Walk the fixture from w at (0,0), then the other hits:

insert ware, house, help, war, our, whole, plus, hot

start (0,0) w
  (0,1) a → (0,2) r   end → "war"
              (0,3) e   end → "ware"
  (1,0) h → (1,1) o → (2,1) l → (2,0) e   end → "whole"

start (1,0) h
  (1,1) o → (1,2) u → (1,3) s → (0,3) e   end → "house"
  (2,0) e → (2,1) l → (2,2) p           end → "help"

start (1,1) o → (1,2) u → (0,2) r         end → "our"

plus: p → l, then u is a diagonal — no child walk
hot:  h → o, then t is not a 4-neighbor of o

The Java is that walk. Bounds first, then skip a marked cell, then ask the trie.

class Solution {
    static final class Node {
        final Node[] children = new Node[26];
        boolean endOfWord;
        String word;
    }

    List<String> findWords(char[][] board, String[] words) {
        Node root = new Node();
        for (String w : words) {
            insert(root, w);
        }
        Set<String> found = new HashSet<>();
        int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        for (int r = 0; r < board.length; r++) {
            for (int c = 0; c < board[0].length; c++) {
                dfs(board, r, c, root, dirs, found);
            }
        }
        return new ArrayList<>(found);
    }

    void insert(Node root, String word) {
        Node node = root;
        for (int i = 0; i < word.length(); i++) {
            int idx = word.charAt(i) - 'a';
            if (node.children[idx] == null) {
                node.children[idx] = new Node();
            }
            node = node.children[idx];
        }
        node.endOfWord = true;
        node.word = word;
    }

    void dfs(char[][] board, int r, int c, Node node, int[][] dirs, Set<String> found) {
        if (r < 0 || r >= board.length || c < 0 || c >= board[0].length) {
            return;
        }
        char ch = board[r][c];
        if (ch == '#') {
            return;
        }
        Node next = node.children[ch - 'a'];
        if (next == null) {
            return;
        }
        if (next.endOfWord) {
            found.add(next.word);
        }
        board[r][c] = '#';
        for (int[] d : dirs) {
            dfs(board, r + d[0], c + d[1], next, dirs, found);
        }
        board[r][c] = ch;
    }
}

Trie insert is O(total characters) — one step per letter. The grid walk is O(mn · 4^L) in the worst case, L the longest word: each of mn cells can start a 4-direction path the trie prunes when a prefix dies. Space is O(total characters) for the trie plus O(L) for the call stack.

Note: Unmark the cell when the recursion returns. Forget the undo and a later start cannot use that tile for a different word. The '#' is the choose; restoring ch is the undo. Do not reach for Unique Paths DP — that prompt counts right-and-down routes, not a dictionary on a 4-direction board.

What interviewers usually poke next

  • Unmark endOfWord after a hit. Clearing the end mark (and the stored word) after you record it skips duplicate paths for that key. The default walk still finds it; this is speed, not a second algorithm.
  • Delete a dead leaf. If a node then has no children and no end mark, drop it from the parent so later walks shrink. Optional cleanup — the same idea as the delete poke on Implement Trie.
  • Word Search. One word, same 4-dir mark/unmark. Do not paste that class here.
  • Add and Search Words. Search DFS-es trie children because . matches any letter. Here the next character is a neighbor cell.
  • Diagonals, or a read-only grid. Eight deltas only if they ask. If mutation is forbidden, a boolean[][] is the mark. Iterative walk uses an ArrayDeque, not java.util.Stack.
  • Aho–Corasick. A production multi-pattern automaton. Not the intended board answer; do not draw it unless they ask for automata.

You are done with this problem when you can say, out loud, why a Word Search per name is correct and too slow, why a missing trie child ends that walk, and why the cell is unmarked when the recursion returns.