DSA-091 · FOCUSED PRACTICE

Word Search II

Advanced · Java 21 · Version 1 · editorial draft

Java reference and baseline verified on JDK 21: 4767 deterministic checks. Learner drafts are not executed.

Understand the problem

Return all distinct dictionary words that can be spelled by an orthogonal path through a letter board, without reusing a board coordinate within one word. Return results in lexicographic order.

board and words are nonnull. The board is rectangular, has at most 12 rows and 12 columns, and contains only lowercase ASCII letters; zero rows or zero columns are allowed. Null/ragged rows or invalid letters throw IllegalArgumentException. Dimension bounds are preconditions. Shared row objects are allowed: coordinates remain distinct cells for path ownership.
words contains at most 10,000 nonnull, nonempty lowercase-ASCII strings of length at most 144 and at most 100,000 total characters. Size bounds are preconditions. Null words throw NullPointerException; empty or invalid words throw IllegalArgumentException. Validate the full board and dictionary even if an empty board would otherwise return immediately.
Preserve every board cell, row reference and dictionary-array element. Return a fresh mutable list of unique words sorted lexicographically, independent across calls. Returned String values may reuse immutable dictionary strings. Orthogonal adjacency excludes diagonals; a coordinate may be reused in another path, but never twice within one path.

Examples

Input: board=[oa,ht]; words=[o,oa,oath,oath,hat,ao,oao]
Output: [ao,o,oa,oath]
The path o→a→t→h finds oath; oa stays searchable after o is emitted. Duplicate input/path occurrences emit one word, and oao would reuse the first o.
Input: board=[aa]; words=[a,aa,aaa,aa]
Output: [a,aa]
Two distinct a coordinates can spell aa, but no third coordinate exists.
Input: board=[ab,cd]; words=[ad,ac,bd]
Output: [ac,bd]
ad would require a diagonal edge and is rejected.

Before you start

Trie terminal words and shared prefixes
Backtracking over orthogonal board paths without coordinate reuse

Recognize the structure

Searching each word independently repeats common board prefixes. A trie lets one board-path prefix serve many dictionary words. The current board path and current trie node are separate state: the same trie prefix may be reached from many coordinate paths.

Your Java attempt

Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.

Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.

Approach, code, and test notes (20,000 characters maximum)

No unsaved text changes · 179/20,000 characters

Self-review

Can I prove used equals precisely the current stack coordinates?Can I explain why clearing a terminal differs from pruning its descendants?Can I account for exponential path exploration and output sorting rather than claiming O(B+S)?

Use the checklist to test your explanation. Checks apply to this visit.

Try before revealing

Hint 1

Several words can share one prefix, so consider a trie.

Hint 2

State must track both the dictionary prefix and the current no-reuse board path.

Hint 3

Mark on entry, consume a terminal only once, continue its descendants, and unmark on backtrack.

Derive the solution

Reveal the baseline, optimized reasoning, and Java code

Search every distinct word separately

Deduplicate/sort dictionary words and run an ordinary per-word board DFS. For each start, match the next character and track a path-local used matrix; unmark on every return. On [aa], a and aa each launch separate traversals. The trie version shares those prefix traversals across words, but board search remains exponential in worst-case path length. The recursive baseline has depth at most 144 under this contract.

Improve the baseline

Build a call-local dictionary trie

Each complete word stores its immutable String in a terminal field. Duplicate dictionary strings share that terminal. After validation, an empty board/dictionary returns a fresh empty list.

Enter matching cells and save a continuation

A frame stores row, column, trie node and nextDirection. Mark the coordinate on push. Explore up/right/down/left using only existing trie edges and unused in-bounds coordinates.

Emit once, continue longer prefixes, then unwind

On first reaching a terminal, append its word and clear only that local terminal. Keep child edges so longer words can still match. When all four directions finish, unmark the coordinate and pop. Sort the final distinct list.

Why it is correct

Path and trie invariant

Stack coordinates form a simple orthogonal path; used is exactly that coordinate set. Its letters equal the prefix represented by the top trie node. A push preserves adjacency, no reuse and prefix membership.

Complete search without global visitation

Every legal dictionary path starts at one scanned coordinate. At each prefix its next valid letter edge and unused neighbor are explored; missing trie edges cannot lead to any dictionary word. Unmarking on pop makes the coordinate available to later paths.

Deduplication without lost extensions

Clearing a terminal after emission removes only an already-reported complete word. Its descendants remain searchable, so longer words are not lost. A fresh trie per call prevents terminal consumption from leaking into later queries; sorting gives the promised deterministic order.

Complete Java reference and baseline

Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.

import java.util.*;
public final class Solution {
    private static final int[][] DIRECTIONS = {{-1,0},{0,1},{1,0},{0,-1}};
    private static final class Node {
        final Node[] children = new Node[26];
        String word;
    }
    private static final class Frame {
        final int row, column;
        final Node node;
        int nextDirection;
        Frame(int row, int column, Node node) { this.row=row; this.column=column; this.node=node; }
    }
    private static int validate(char[][] board, String[] words) {
        Objects.requireNonNull(board,"board"); Objects.requireNonNull(words,"words");
        int columns = board.length == 0 ? 0 : board[0] == null ? -1 : board[0].length;
        for (char[] row : board) {
            if (row == null || row.length != columns) throw new IllegalArgumentException("nonrectangular board");
            for (char c : row) if (c < 'a' || c > 'z') throw new IllegalArgumentException("invalid board letter");
        }
        for (String word : words) {
            Objects.requireNonNull(word,"word");
            if (word.isEmpty()) throw new IllegalArgumentException("empty dictionary word");
            for (int i=0;i<word.length();i++) if (word.charAt(i) < 'a' || word.charAt(i) > 'z') throw new IllegalArgumentException("invalid dictionary letter");
        }
        return columns;
    }
    private static void enter(int row, int column, Node node, boolean[][] used, ArrayDeque<Frame> stack, List<String> result) {
        used[row][column] = true;
        stack.push(new Frame(row,column,node));
        if (node.word != null) { result.add(node.word); node.word = null; }
    }
    public static List<String> findWords(char[][] board, String[] words) {
        int columns = validate(board,words);
        List<String> result = new ArrayList<>();
        if (board.length == 0 || columns == 0 || words.length == 0) return result;
        Node root = new Node();
        for (String word : words) {
            Node node = root;
            for (int i=0;i<word.length();i++) {
                int slot = word.charAt(i)-'a';
                if (node.children[slot] == null) node.children[slot] = new Node();
                node = node.children[slot];
            }
            node.word = word;
        }
        boolean[][] used = new boolean[board.length][columns];
        ArrayDeque<Frame> stack = new ArrayDeque<>();
        for (int row=0;row<board.length;row++) for (int column=0;column<columns;column++) {
            Node start = root.children[board[row][column]-'a'];
            if (start == null) continue;
            enter(row,column,start,used,stack,result);
            while (!stack.isEmpty()) {
                Frame frame = stack.peek();
                if (frame.nextDirection == 4) { used[frame.row][frame.column] = false; stack.pop(); continue; }
                int direction = frame.nextDirection++;
                int nr = frame.row+DIRECTIONS[direction][0], nc = frame.column+DIRECTIONS[direction][1];
                if (nr < 0 || nr >= board.length || nc < 0 || nc >= columns || used[nr][nc]) continue;
                Node child = frame.node.children[board[nr][nc]-'a'];
                if (child == null) continue;
                enter(nr,nc,child,used,stack,result);
            }
        }
        Collections.sort(result);
        return result;
    }
    private static boolean visit(char[][] board, String word, int index, int row, int column, boolean[][] used) {
        if (row < 0 || row >= board.length || column < 0 || column >= board[0].length || used[row][column] || board[row][column] != word.charAt(index)) return false;
        if (index+1 == word.length()) return true;
        used[row][column] = true;
        boolean found = false;
        for (int[] direction : DIRECTIONS) if (visit(board,word,index+1,row+direction[0],column+direction[1],used)) { found=true; break; }
        used[row][column] = false;
        return found;
    }
    public static List<String> baseline(char[][] board, String[] words) {
        int columns = validate(board,words);
        List<String> result = new ArrayList<>();
        if (board.length == 0 || columns == 0) return result;
        for (String word : new TreeSet<>(Arrays.asList(words))) {
            boolean[][] used = new boolean[board.length][columns]; boolean found = false;
            for (int row=0;row<board.length&&!found;row++) for (int column=0;column<columns;column++) if (visit(board,word,0,row,column,used)) { found=true; break; }
            if (found) result.add(word);
        }
        return result;
    }
}

Read the meaningful blocks

Use coordinates, not letter values, as visited keys

Two a cells are distinct resources. Using a separate boolean matrix also preserves aliased source row objects.

Advance nextDirection before descending

The suspended parent resumes at its next untried direction after the child returns; it must not retry the same edge indefinitely.

Separate terminal lifetime from used lifetime

A consumed terminal lasts until this call ends; a used cell lasts only until its path frame is popped. Trie edges are not globally pruned in this implementation.

Complexity

Let B be board cells, S dictionary characters, Q emitted unique words, L=min(B,longest dictionary word length), and E the number of matching board-prefix path entries explored. Time is O(S+B+E+Q L log(Q+1)), including validation and lexicographic output comparisons. For L>=1 a loose worst-case path bound is E=O(B·4·3^(L−1)); the first move has at most four choices and later moves exclude the predecessor. Trie pruning improves actual work, not this worst-case exponential nature.

Auxiliary storage is O(S+B+L): fixed-alphabet trie, used matrix and live path frames. Output retains O(Q) String references; source strings are immutable. For the baseline, let K be input word occurrences, M maximum dictionary word length, and E_w attempted board-path states for each distinct word w, including failed start checks. Its time is O(S+B+K M log(K+1)+sum_w E_w), including ordered-set string comparisons even for words longer than the board. For D distinct words, baseline auxiliary storage is O(D+B+L), excluding O(Q) returned references. Recursive depth is bounded by at most 144 cells.

Exact-state walkthroughs

Reveal normal and boundary traces

Shared prefixes, duplicate words, and local terminal consumption

Input: {"board":["oa","ht"],"words":["o","oa","oath","oath","hat","ao","oao"]} · Unique sorted found words: ["ao","o","oa","oath"]

Step 1 of 42: Validate all inputs before building or taking an empty-board return.

Board coordinates are separate from shared trie prefixes. The board never changes; used marks only the current simple path.

Board search — trie prefixes and path-local coordinate ownership

Phase: initial.

Trie paths — sorted logical display

(root / empty path)prefix path only
aprefix path only
aoterminal word
hprefix path only
haprefix path only
hatterminal word
oterminal word
oaterminal word
oaoterminal word
oatprefix path only
oathterminal word

✓ means this coordinate belongs to the current path. The source letters never change.

Path continuations — stack top at right

Empty.

Words found so far — discovery order

Empty.

Direction indices 0–3 mean up, right, down, left; 4 means backtrack. A terminal is consumed for this whole call, while a used coordinate is released on pop. Finding a prefix word keeps its descendant edges available.

Path cards represent shared dictionary prefixes, not board cells or dictionary occurrence order. Complete exact state and equivalent static steps remain available below.

State after this step
Variable	Value
board	`["oa","ht"]`
words	`["o","oa","oath","oath","hat","ao","oao"]`
paths	`["","a","ao","h","ha","hat","o","oa","oao","oat","oath"]`
remainingWords	`["ao","hat","o","oa","oao","oath"]`
found	`[]`
stack	`[]`
used	`[[false,false],[false,false]]`
phase	`"initial"`
current	`null`

See the affected Java block

 1 import java.util.*;
 2 public final class Solution {
 3     private static final int[][] DIRECTIONS = {{-1,0},{0,1},{1,0},{0,-1}};
 4     private static final class Node {
 5         final Node[] children = new Node[26];
 6         String word;
 7     }
 8     private static final class Frame {
 9         final int row, column;
10         final Node node;
11         int nextDirection;
12         Frame(int row, int column, Node node) { this.row=row; this.column=column; this.node=node; }
13     }
14     private static int validate(char[][] board, String[] words) {
15         Objects.requireNonNull(board,"board"); Objects.requireNonNull(words,"words");
16         int columns = board.length == 0 ? 0 : board[0] == null ? -1 : board[0].length;
17         for (char[] row : board) {
18             if (row == null || row.length != columns) throw new IllegalArgumentException("nonrectangular board");
19             for (char c : row) if (c < 'a' || c > 'z') throw new IllegalArgumentException("invalid board letter");
20         }
21         for (String word : words) {
22             Objects.requireNonNull(word,"word");
23             if (word.isEmpty()) throw new IllegalArgumentException("empty dictionary word");
24             for (int i=0;i<word.length();i++) if (word.charAt(i) < 'a' || word.charAt(i) > 'z') throw new IllegalArgumentException("invalid dictionary letter");
25         }
26         return columns;
27     }
28     private static void enter(int row, int column, Node node, boolean[][] used, ArrayDeque<Frame> stack, List<String> result) {
29         used[row][column] = true;
30         stack.push(new Frame(row,column,node));
31         if (node.word != null) { result.add(node.word); node.word = null; }
32     }
33     public static List<String> findWords(char[][] board, String[] words) {
34         int columns = validate(board,words);
35         List<String> result = new ArrayList<>();
36         if (board.length == 0 || columns == 0 || words.length == 0) return result;
37         Node root = new Node();
38         for (String word : words) {
39             Node node = root;
40             for (int i=0;i<word.length();i++) {
41                 int slot = word.charAt(i)-'a';
42                 if (node.children[slot] == null) node.children[slot] = new Node();
43                 node = node.children[slot];
44             }
45             node.word = word;
46         }
47         boolean[][] used = new boolean[board.length][columns];
48         ArrayDeque<Frame> stack = new ArrayDeque<>();
49         for (int row=0;row<board.length;row++) for (int column=0;column<columns;column++) {
50             Node start = root.children[board[row][column]-'a'];
51             if (start == null) continue;
52             enter(row,column,start,used,stack,result);
53             while (!stack.isEmpty()) {
54                 Frame frame = stack.peek();
55                 if (frame.nextDirection == 4) { used[frame.row][frame.column] = false; stack.pop(); continue; }
56                 int direction = frame.nextDirection++;
57                 int nr = frame.row+DIRECTIONS[direction][0], nc = frame.column+DIRECTIONS[direction][1];
58                 if (nr < 0 || nr >= board.length || nc < 0 || nc >= columns || used[nr][nc]) continue;
59                 Node child = frame.node.children[board[nr][nc]-'a'];
60                 if (child == null) continue;
61                 enter(nr,nc,child,used,stack,result);
62             }
63         }
64         Collections.sort(result);
65         return result;
66     }
67     private static boolean visit(char[][] board, String word, int index, int row, int column, boolean[][] used) {
68         if (row < 0 || row >= board.length || column < 0 || column >= board[0].length || used[row][column] || board[row][column] != word.charAt(index)) return false;
69         if (index+1 == word.length()) return true;
70         used[row][column] = true;
71         boolean found = false;
72         for (int[] direction : DIRECTIONS) if (visit(board,word,index+1,row+direction[0],column+direction[1],used)) { found=true; break; }
73         used[row][column] = false;
74         return found;
75     }
76     public static List<String> baseline(char[][] board, String[] words) {
77         int columns = validate(board,words);
78         List<String> result = new ArrayList<>();
79         if (board.length == 0 || columns == 0) return result;
80         for (String word : new TreeSet<>(Arrays.asList(words))) {
81             boolean[][] used = new boolean[board.length][columns]; boolean found = false;
82             for (int row=0;row<board.length&&!found;row++) for (int column=0;column<columns;column++) if (visit(board,word,0,row,column,used)) { found=true; break; }
83             if (found) result.add(word);
84         }
85         return result;
86     }
87 }
88

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Validate all inputs before building or taking an empty-board return.
Board coordinates are separate from shared trie prefixes. The board never changes; used marks only the current simple path.
board
["oa","ht"]
words
["o","oa","oath","oath","hat","ao","oao"]
paths
["","a","ao","h","ha","hat","o","oa","oao","oat","oath"]
remainingWords
["ao","hat","o","oa","oao","oath"]
found
[]
stack
[]
used
[[false,false],[false,false]]
phase
"initial"
current
null
Enter one start cell and consume a terminal word at most once.
Clearing a local terminal deduplicates output; its child edges remain available for longer words.
board
["oa","ht"]
words
["o","oa","oath","oath","hat","ao","oao"]
paths
["","a","ao","h","ha","hat","o","oa","oao","oat","oath"]
remainingWords
["ao","hat","oa","oao","oath"]
found
["o"]
stack
[{"row":0,"column":0,"prefix":"o","nextDirection":0}]
used
[[true,false],[false,false]]
phase
"enter-start"
current
[0,0]
startIndex
0
matched
"o"
Reject one neighbor while preserving the current path.
Direction order is up, right, down, left. A used coordinate cannot be reused, even if its letter would extend a trie path.
board
["oa","ht"]
words
["o","oa","oath","oath","hat","ao","oao"]
paths
["","a","ao","h","ha","hat","o","oa","oao","oat","oath"]
remainingWords
["ao","hat","oa","oao","oath"]
found
["o"]
stack
[{"row":0,"column":0,"prefix":"o","nextDirection":1}]
used
[[true,false],[false,false]]
phase
"skip"
current
[0,0]
probe
[-1,0]
direction
0
reason
"outside"
Extend the simple path along an existing trie edge.
A shared trie node may be reached by many board paths. Only its local terminal is cleared after the first emitted occurrence.
board
["oa","ht"]
words
["o","oa","oath","oath","hat","ao","oao"]
paths
["","a","ao","h","ha","hat","o","oa","oao","oat","oath"]
remainingWords
["ao","hat","oao","oath"]
found
["o","oa"]
stack
[{"row":0,"column":0,"prefix":"o","nextDirection":2},{"row":0,"column":1,"prefix":"oa","nextDirection":0}]
used
[[true,true],[false,false]]
phase
"enter"
current
[0,1]
direction
1
matched
"oa"
Reject one neighbor while preserving the current path.
Direction order is up, right, down, left. A used coordinate cannot be reused, even if its letter would extend a trie path.
board
["oa","ht"]
words
["o","oa","oath","oath","hat","ao","oao"]
paths
["","a","ao","h","ha","hat","o","oa","oao","oat","oath"]
remainingWords
["ao","hat","oao","oath"]
found
["o","oa"]
stack
[{"row":0,"column":0,"prefix":"o","nextDirection":2},{"row":0,"column":1,"prefix":"oa","nextDirection":1}]
used
[[true,true],[false,false]]
phase
"skip"
current
[0,1]
probe
[-1,1]
direction
0
reason
"outside"
Reject one neighbor while preserving the current path.
Direction order is up, right, down, left. A used coordinate cannot be reused, even if its letter would extend a trie path.
board
["oa","ht"]
words
["o","oa","oath","oath","hat","ao","oao"]
paths
["","a","ao","h","ha","hat","o","oa","oao","oat","oath"]
remainingWords
["ao","hat","oao","oath"]
found
["o","oa"]
stack
[{"row":0,"column":0,"prefix":"o","nextDirection":2},{"row":0,"column":1,"prefix":"oa","nextDirection":2}]
used
[[true,true],[false,false]]
phase
"skip"
current
[0,1]
probe
[0,2]
direction
1
reason
"outside"
Extend the simple path along an existing trie edge.
A shared trie node may be reached by many board paths. Only its local terminal is cleared after the first emitted occurrence.
board
["oa","ht"]
words
["o","oa","oath","oath","hat","ao","oao"]
paths
["","a","ao","h","ha","hat","o","oa","oao","oat","oath"]
remainingWords
["ao","hat","oao","oath"]
found
["o","oa"]
stack
[{"row":0,"column":0,"prefix":"o","nextDirection":2},{"row":0,"column":1,"prefix":"oa","nextDirection":3},{"row":1,"column":1,"prefix":"oat","nextDirection":0}]
used
[[true,true],[false,true]]
phase
"enter"
current
[1,1]
direction
2
matched
null
Reject one neighbor while preserving the current path.
Direction order is up, right, down, left. A used coordinate cannot be reused, even if its letter would extend a trie path.
board
["oa","ht"]
words
["o","oa","oath","oath","hat","ao","oao"]
paths
["","a","ao","h","ha","hat","o","oa","oao","oat","oath"]
remainingWords
["ao","hat","oao","oath"]
found
["o","oa"]
stack
[{"row":0,"column":0,"prefix":"o","nextDirection":2},{"row":0,"column":1,"prefix":"oa","nextDirection":3},{"row":1,"column":1,"prefix":"oat","nextDirection":1}]
used
[[true,true],[false,true]]
phase
"skip"
current
[1,1]
probe
[0,1]
direction
0
reason
"used"
Reject one neighbor while preserving the current path.
Direction order is up, right, down, left. A used coordinate cannot be reused, even if its letter would extend a trie path.
board
["oa","ht"]
words
["o","oa","oath","oath","hat","ao","oao"]
paths
["","a","ao","h","ha","hat","o","oa","oao","oat","oath"]
remainingWords
["ao","hat","oao","oath"]
found
["o","oa"]
stack
[{"row":0,"column":0,"prefix":"o","nextDirection":2},{"row":0,"column":1,"prefix":"oa","nextDirection":3},{"row":1,"column":1,"prefix":"oat","nextDirection":2}]
used
[[true,true],[false,true]]
phase
"skip"
current
[1,1]
probe
[1,2]
direction
1
reason
"outside"
Reject one neighbor while preserving the current path.
Direction order is up, right, down, left. A used coordinate cannot be reused, even if its letter would extend a trie path.
board
["oa","ht"]
words
["o","oa","oath","oath","hat","ao","oao"]
paths
["","a","ao","h","ha","hat","o","oa","oao","oat","oath"]
remainingWords
["ao","hat","oao","oath"]
found
["o","oa"]
stack
[{"row":0,"column":0,"prefix":"o","nextDirection":2},{"row":0,"column":1,"prefix":"oa","nextDirection":3},{"row":1,"column":1,"prefix":"oat","nextDirection":3}]
used
[[true,true],[false,true]]
phase
"skip"
current
[1,1]
probe
[2,1]
direction
2
reason
"outside"
Extend the simple path along an existing trie edge.
A shared trie node may be reached by many board paths. Only its local terminal is cleared after the first emitted occurrence.
board
["oa","ht"]
words
["o","oa","oath","oath","hat","ao","oao"]
paths
["","a","ao","h","ha","hat","o","oa","oao","oat","oath"]
remainingWords
["ao","hat","oao"]
found
["o","oa","oath"]
stack
[{"row":0,"column":0,"prefix":"o","nextDirection":2},{"row":0,"column":1,"prefix":"oa","nextDirection":3},{"row":1,"column":1,"prefix":"oat","nextDirection":4},{"row":1,"column":0,"prefix":"oath","nextDirection":0}]
used
[[true,true],[true,true]]
phase
"enter"
current
[1,0]
direction
3
matched
"oath"
Reject one neighbor while preserving the current path.
Direction order is up, right, down, left. A used coordinate cannot be reused, even if its letter would extend a trie path.
board
["oa","ht"]
words
["o","oa","oath","oath","hat","ao","oao"]
paths
["","a","ao","h","ha","hat","o","oa","oao","oat","oath"]
remainingWords
["ao","hat","oao"]
found
["o","oa","oath"]
stack
[{"row":0,"column":0,"prefix":"o","nextDirection":2},{"row":0,"column":1,"prefix":"oa","nextDirection":3},{"row":1,"column":1,"prefix":"oat","nextDirection":4},{"row":1,"column":0,"prefix":"oath","nextDirection":1}]
used
[[true,true],[true,true]]
phase
"skip"
current
[1,0]
probe
[0,0]
direction
0
reason
"used"
Reject one neighbor while preserving the current path.
Direction order is up, right, down, left. A used coordinate cannot be reused, even if its letter would extend a trie path.
board
["oa","ht"]
words
["o","oa","oath","oath","hat","ao","oao"]
paths
["","a","ao","h","ha","hat","o","oa","oao","oat","oath"]
remainingWords
["ao","hat","oao"]
found
["o","oa","oath"]
stack
[{"row":0,"column":0,"prefix":"o","nextDirection":2},{"row":0,"column":1,"prefix":"oa","nextDirection":3},{"row":1,"column":1,"prefix":"oat","nextDirection":4},{"row":1,"column":0,"prefix":"oath","nextDirection":2}]
used
[[true,true],[true,true]]
phase
"skip"
current
[1,0]
probe
[1,1]
direction
1
reason
"used"
Reject one neighbor while preserving the current path.
Direction order is up, right, down, left. A used coordinate cannot be reused, even if its letter would extend a trie path.
board
["oa","ht"]
words
["o","oa","oath","oath","hat","ao","oao"]
paths
["","a","ao","h","ha","hat","o","oa","oao","oat","oath"]
remainingWords
["ao","hat","oao"]
found
["o","oa","oath"]
stack
[{"row":0,"column":0,"prefix":"o","nextDirection":2},{"row":0,"column":1,"prefix":"oa","nextDirection":3},{"row":1,"column":1,"prefix":"oat","nextDirection":4},{"row":1,"column":0,"prefix":"oath","nextDirection":3}]
used
[[true,true],[true,true]]
phase
"skip"
current
[1,0]
probe
[2,0]
direction
2
reason
"outside"
Reject one neighbor while preserving the current path.
Direction order is up, right, down, left. A used coordinate cannot be reused, even if its letter would extend a trie path.
board
["oa","ht"]
words
["o","oa","oath","oath","hat","ao","oao"]
paths
["","a","ao","h","ha","hat","o","oa","oao","oat","oath"]
remainingWords
["ao","hat","oao"]
found
["o","oa","oath"]
stack
[{"row":0,"column":0,"prefix":"o","nextDirection":2},{"row":0,"column":1,"prefix":"oa","nextDirection":3},{"row":1,"column":1,"prefix":"oat","nextDirection":4},{"row":1,"column":0,"prefix":"oath","nextDirection":4}]
used
[[true,true],[true,true]]
phase
"skip"
current
[1,0]
probe
[1,-1]
direction
3
reason
"outside"
Backtrack after all four directions and release this coordinate.
The used matrix equals exactly the coordinates still on the stack. This cell may be reused by another path.
board
["oa","ht"]
words
["o","oa","oath","oath","hat","ao","oao"]
paths
["","a","ao","h","ha","hat","o","oa","oao","oat","oath"]
remainingWords
["ao","hat","oao"]
found
["o","oa","oath"]
stack
[{"row":0,"column":0,"prefix":"o","nextDirection":2},{"row":0,"column":1,"prefix":"oa","nextDirection":3},{"row":1,"column":1,"prefix":"oat","nextDirection":4}]
used
[[true,true],[false,true]]
phase
"backtrack"
current
[1,0]
Backtrack after all four directions and release this coordinate.
The used matrix equals exactly the coordinates still on the stack. This cell may be reused by another path.
board
["oa","ht"]
words
["o","oa","oath","oath","hat","ao","oao"]
paths
["","a","ao","h","ha","hat","o","oa","oao","oat","oath"]
remainingWords
["ao","hat","oao"]
found
["o","oa","oath"]
stack
[{"row":0,"column":0,"prefix":"o","nextDirection":2},{"row":0,"column":1,"prefix":"oa","nextDirection":3}]
used
[[true,true],[false,false]]
phase
"backtrack"
current
[1,1]
Reject one neighbor while preserving the current path.
Direction order is up, right, down, left. A used coordinate cannot be reused, even if its letter would extend a trie path.
board
["oa","ht"]
words
["o","oa","oath","oath","hat","ao","oao"]
paths
["","a","ao","h","ha","hat","o","oa","oao","oat","oath"]
remainingWords
["ao","hat","oao"]
found
["o","oa","oath"]
stack
[{"row":0,"column":0,"prefix":"o","nextDirection":2},{"row":0,"column":1,"prefix":"oa","nextDirection":4}]
used
[[true,true],[false,false]]
phase
"skip"
current
[0,1]
probe
[0,0]
direction
3
reason
"used"
Backtrack after all four directions and release this coordinate.
The used matrix equals exactly the coordinates still on the stack. This cell may be reused by another path.
board
["oa","ht"]
words
["o","oa","oath","oath","hat","ao","oao"]
paths
["","a","ao","h","ha","hat","o","oa","oao","oat","oath"]
remainingWords
["ao","hat","oao"]
found
["o","oa","oath"]
stack
[{"row":0,"column":0,"prefix":"o","nextDirection":2}]
used
[[true,false],[false,false]]
phase
"backtrack"
current
[0,1]
Reject one neighbor while preserving the current path.
Direction order is up, right, down, left. A used coordinate cannot be reused, even if its letter would extend a trie path.
board
["oa","ht"]
words
["o","oa","oath","oath","hat","ao","oao"]
paths
["","a","ao","h","ha","hat","o","oa","oao","oat","oath"]
remainingWords
["ao","hat","oao"]
found
["o","oa","oath"]
stack
[{"row":0,"column":0,"prefix":"o","nextDirection":3}]
used
[[true,false],[false,false]]
phase
"skip"
current
[0,0]
probe
[1,0]
direction
2
reason
"no-prefix"
Reject one neighbor while preserving the current path.
Direction order is up, right, down, left. A used coordinate cannot be reused, even if its letter would extend a trie path.
board
["oa","ht"]
words
["o","oa","oath","oath","hat","ao","oao"]
paths
["","a","ao","h","ha","hat","o","oa","oao","oat","oath"]
remainingWords
["ao","hat","oao"]
found
["o","oa","oath"]
stack
[{"row":0,"column":0,"prefix":"o","nextDirection":4}]
used
[[true,false],[false,false]]
phase
"skip"
current
[0,0]
probe
[0,-1]
direction
3
reason
"outside"
Backtrack after all four directions and release this coordinate.
The used matrix equals exactly the coordinates still on the stack. This cell may be reused by another path.
board
["oa","ht"]
words
["o","oa","oath","oath","hat","ao","oao"]
paths
["","a","ao","h","ha","hat","o","oa","oao","oat","oath"]
remainingWords
["ao","hat","oao"]
found
["o","oa","oath"]
stack
[]
used
[[false,false],[false,false]]
phase
"backtrack"
current
[0,0]
Enter one start cell and consume a terminal word at most once.
Clearing a local terminal deduplicates output; its child edges remain available for longer words.
board
["oa","ht"]
words
["o","oa","oath","oath","hat","ao","oao"]
paths
["","a","ao","h","ha","hat","o","oa","oao","oat","oath"]
remainingWords
["ao","hat","oao"]
found
["o","oa","oath"]
stack
[{"row":0,"column":1,"prefix":"a","nextDirection":0}]
used
[[false,true],[false,false]]
phase
"enter-start"
current
[0,1]
startIndex
1
matched
null
Reject one neighbor while preserving the current path.
Direction order is up, right, down, left. A used coordinate cannot be reused, even if its letter would extend a trie path.
board
["oa","ht"]
words
["o","oa","oath","oath","hat","ao","oao"]
paths
["","a","ao","h","ha","hat","o","oa","oao","oat","oath"]
remainingWords
["ao","hat","oao"]
found
["o","oa","oath"]
stack
[{"row":0,"column":1,"prefix":"a","nextDirection":1}]
used
[[false,true],[false,false]]
phase
"skip"
current
[0,1]
probe
[-1,1]
direction
0
reason
"outside"
Reject one neighbor while preserving the current path.
Direction order is up, right, down, left. A used coordinate cannot be reused, even if its letter would extend a trie path.
board
["oa","ht"]
words
["o","oa","oath","oath","hat","ao","oao"]
paths
["","a","ao","h","ha","hat","o","oa","oao","oat","oath"]
remainingWords
["ao","hat","oao"]
found
["o","oa","oath"]
stack
[{"row":0,"column":1,"prefix":"a","nextDirection":2}]
used
[[false,true],[false,false]]
phase
"skip"
current
[0,1]
probe
[0,2]
direction
1
reason
"outside"
Reject one neighbor while preserving the current path.
Direction order is up, right, down, left. A used coordinate cannot be reused, even if its letter would extend a trie path.
board
["oa","ht"]
words
["o","oa","oath","oath","hat","ao","oao"]
paths
["","a","ao","h","ha","hat","o","oa","oao","oat","oath"]
remainingWords
["ao","hat","oao"]
found
["o","oa","oath"]
stack
[{"row":0,"column":1,"prefix":"a","nextDirection":3}]
used
[[false,true],[false,false]]
phase
"skip"
current
[0,1]
probe
[1,1]
direction
2
reason
"no-prefix"
Extend the simple path along an existing trie edge.
A shared trie node may be reached by many board paths. Only its local terminal is cleared after the first emitted occurrence.
board
["oa","ht"]
words
["o","oa","oath","oath","hat","ao","oao"]
paths
["","a","ao","h","ha","hat","o","oa","oao","oat","oath"]
remainingWords
["hat","oao"]
found
["o","oa","oath","ao"]
stack
[{"row":0,"column":1,"prefix":"a","nextDirection":4},{"row":0,"column":0,"prefix":"ao","nextDirection":0}]
used
[[true,true],[false,false]]
phase
"enter"
current
[0,0]
direction
3
matched
"ao"
Reject one neighbor while preserving the current path.
Direction order is up, right, down, left. A used coordinate cannot be reused, even if its letter would extend a trie path.
board
["oa","ht"]
words
["o","oa","oath","oath","hat","ao","oao"]
paths
["","a","ao","h","ha","hat","o","oa","oao","oat","oath"]
remainingWords
["hat","oao"]
found
["o","oa","oath","ao"]
stack
[{"row":0,"column":1,"prefix":"a","nextDirection":4},{"row":0,"column":0,"prefix":"ao","nextDirection":1}]
used
[[true,true],[false,false]]
phase
"skip"
current
[0,0]
probe
[-1,0]
direction
0
reason
"outside"
Reject one neighbor while preserving the current path.
Direction order is up, right, down, left. A used coordinate cannot be reused, even if its letter would extend a trie path.
board
["oa","ht"]
words
["o","oa","oath","oath","hat","ao","oao"]
paths
["","a","ao","h","ha","hat","o","oa","oao","oat","oath"]
remainingWords
["hat","oao"]
found
["o","oa","oath","ao"]
stack
[{"row":0,"column":1,"prefix":"a","nextDirection":4},{"row":0,"column":0,"prefix":"ao","nextDirection":2}]
used
[[true,true],[false,false]]
phase
"skip"
current
[0,0]
probe
[0,1]
direction
1
reason
"used"
Reject one neighbor while preserving the current path.
Direction order is up, right, down, left. A used coordinate cannot be reused, even if its letter would extend a trie path.
board
["oa","ht"]
words
["o","oa","oath","oath","hat","ao","oao"]
paths
["","a","ao","h","ha","hat","o","oa","oao","oat","oath"]
remainingWords
["hat","oao"]
found
["o","oa","oath","ao"]
stack
[{"row":0,"column":1,"prefix":"a","nextDirection":4},{"row":0,"column":0,"prefix":"ao","nextDirection":3}]
used
[[true,true],[false,false]]
phase
"skip"
current
[0,0]
probe
[1,0]
direction
2
reason
"no-prefix"
Reject one neighbor while preserving the current path.
Direction order is up, right, down, left. A used coordinate cannot be reused, even if its letter would extend a trie path.
board
["oa","ht"]
words
["o","oa","oath","oath","hat","ao","oao"]
paths
["","a","ao","h","ha","hat","o","oa","oao","oat","oath"]
remainingWords
["hat","oao"]
found
["o","oa","oath","ao"]
stack
[{"row":0,"column":1,"prefix":"a","nextDirection":4},{"row":0,"column":0,"prefix":"ao","nextDirection":4}]
used
[[true,true],[false,false]]
phase
"skip"
current
[0,0]
probe
[0,-1]
direction
3
reason
"outside"
Backtrack after all four directions and release this coordinate.
The used matrix equals exactly the coordinates still on the stack. This cell may be reused by another path.
board
["oa","ht"]
words
["o","oa","oath","oath","hat","ao","oao"]
paths
["","a","ao","h","ha","hat","o","oa","oao","oat","oath"]
remainingWords
["hat","oao"]
found
["o","oa","oath","ao"]
stack
[{"row":0,"column":1,"prefix":"a","nextDirection":4}]
used
[[false,true],[false,false]]
phase
"backtrack"
current
[0,0]
Backtrack after all four directions and release this coordinate.
The used matrix equals exactly the coordinates still on the stack. This cell may be reused by another path.
board
["oa","ht"]
words
["o","oa","oath","oath","hat","ao","oao"]
paths
["","a","ao","h","ha","hat","o","oa","oao","oat","oath"]
remainingWords
["hat","oao"]
found
["o","oa","oath","ao"]
stack
[]
used
[[false,false],[false,false]]
phase
"backtrack"
current
[0,1]
Enter one start cell and consume a terminal word at most once.
Clearing a local terminal deduplicates output; its child edges remain available for longer words.
board
["oa","ht"]
words
["o","oa","oath","oath","hat","ao","oao"]
paths
["","a","ao","h","ha","hat","o","oa","oao","oat","oath"]
remainingWords
["hat","oao"]
found
["o","oa","oath","ao"]
stack
[{"row":1,"column":0,"prefix":"h","nextDirection":0}]
used
[[false,false],[true,false]]
phase
"enter-start"
current
[1,0]
startIndex
2
matched
null
Reject one neighbor while preserving the current path.
Direction order is up, right, down, left. A used coordinate cannot be reused, even if its letter would extend a trie path.
board
["oa","ht"]
words
["o","oa","oath","oath","hat","ao","oao"]
paths
["","a","ao","h","ha","hat","o","oa","oao","oat","oath"]
remainingWords
["hat","oao"]
found
["o","oa","oath","ao"]
stack
[{"row":1,"column":0,"prefix":"h","nextDirection":1}]
used
[[false,false],[true,false]]
phase
"skip"
current
[1,0]
probe
[0,0]
direction
0
reason
"no-prefix"
Reject one neighbor while preserving the current path.
Direction order is up, right, down, left. A used coordinate cannot be reused, even if its letter would extend a trie path.
board
["oa","ht"]
words
["o","oa","oath","oath","hat","ao","oao"]
paths
["","a","ao","h","ha","hat","o","oa","oao","oat","oath"]
remainingWords
["hat","oao"]
found
["o","oa","oath","ao"]
stack
[{"row":1,"column":0,"prefix":"h","nextDirection":2}]
used
[[false,false],[true,false]]
phase
"skip"
current
[1,0]
probe
[1,1]
direction
1
reason
"no-prefix"
Reject one neighbor while preserving the current path.
Direction order is up, right, down, left. A used coordinate cannot be reused, even if its letter would extend a trie path.
board
["oa","ht"]
words
["o","oa","oath","oath","hat","ao","oao"]
paths
["","a","ao","h","ha","hat","o","oa","oao","oat","oath"]
remainingWords
["hat","oao"]
found
["o","oa","oath","ao"]
stack
[{"row":1,"column":0,"prefix":"h","nextDirection":3}]
used
[[false,false],[true,false]]
phase
"skip"
current
[1,0]
probe
[2,0]
direction
2
reason
"outside"
Reject one neighbor while preserving the current path.
Direction order is up, right, down, left. A used coordinate cannot be reused, even if its letter would extend a trie path.
board
["oa","ht"]
words
["o","oa","oath","oath","hat","ao","oao"]
paths
["","a","ao","h","ha","hat","o","oa","oao","oat","oath"]
remainingWords
["hat","oao"]
found
["o","oa","oath","ao"]
stack
[{"row":1,"column":0,"prefix":"h","nextDirection":4}]
used
[[false,false],[true,false]]
phase
"skip"
current
[1,0]
probe
[1,-1]
direction
3
reason
"outside"
Backtrack after all four directions and release this coordinate.
The used matrix equals exactly the coordinates still on the stack. This cell may be reused by another path.
board
["oa","ht"]
words
["o","oa","oath","oath","hat","ao","oao"]
paths
["","a","ao","h","ha","hat","o","oa","oao","oat","oath"]
remainingWords
["hat","oao"]
found
["o","oa","oath","ao"]
stack
[]
used
[[false,false],[false,false]]
phase
"backtrack"
current
[1,0]
Skip a start cell with no root trie edge.
A dictionary word cannot begin at this cell, but later starts are still considered.
board
["oa","ht"]
words
["o","oa","oath","oath","hat","ao","oao"]
paths
["","a","ao","h","ha","hat","o","oa","oao","oat","oath"]
remainingWords
["hat","oao"]
found
["o","oa","oath","ao"]
stack
[]
used
[[false,false],[false,false]]
phase
"start-missing"
current
[1,1]
startIndex
3
Sort the distinct found words for a deterministic API result.
Every start path is exhausted and all used flags are false. Terminal clearing is call-local; a later findWords call builds a fresh trie.
board
["oa","ht"]
words
["o","oa","oath","oath","hat","ao","oao"]
paths
["","a","ao","h","ha","hat","o","oa","oao","oat","oath"]
remainingWords
["hat","oao"]
found
["ao","o","oa","oath"]
stack
[]
used
[[false,false],[false,false]]
phase
"sorted"
current
null
Return the documented operation outcomes, unique found words, or exact replacement text.
Trie path displays are logical views. Board-path visited state and terminal flags have different lifetimes; no caller-owned input is mutated.
result
["ao","o","oa","oath"]

Repeated letters require distinct coordinates

Input: {"board":["aa"],"words":["a","aa","aaa","aa"]} · Unique sorted found words: ["a","aa"]

Step 1 of 25: Validate all inputs before building or taking an empty-board return.

Board coordinates are separate from shared trie prefixes. The board never changes; used marks only the current simple path.

Board search — trie prefixes and path-local coordinate ownership

Phase: initial.

Trie paths — sorted logical display

(root / empty path)prefix path only
aterminal word
aaterminal word
aaaterminal word

✓ means this coordinate belongs to the current path. The source letters never change.

Path continuations — stack top at right

Empty.

Words found so far — discovery order

Empty.

Path cards represent shared dictionary prefixes, not board cells or dictionary occurrence order. Complete exact state and equivalent static steps remain available below.

State after this step
Variable	Value
board	`["aa"]`
words	`["a","aa","aaa","aa"]`
paths	`["","a","aa","aaa"]`
remainingWords	`["a","aa","aaa"]`
found	`[]`
stack	`[]`
used	`[[false,false]]`
phase	`"initial"`
current	`null`

See the affected Java block

 1 import java.util.*;
 2 public final class Solution {
 3     private static final int[][] DIRECTIONS = {{-1,0},{0,1},{1,0},{0,-1}};
 4     private static final class Node {
 5         final Node[] children = new Node[26];
 6         String word;
 7     }
 8     private static final class Frame {
 9         final int row, column;
10         final Node node;
11         int nextDirection;
12         Frame(int row, int column, Node node) { this.row=row; this.column=column; this.node=node; }
13     }
14     private static int validate(char[][] board, String[] words) {
15         Objects.requireNonNull(board,"board"); Objects.requireNonNull(words,"words");
16         int columns = board.length == 0 ? 0 : board[0] == null ? -1 : board[0].length;
17         for (char[] row : board) {
18             if (row == null || row.length != columns) throw new IllegalArgumentException("nonrectangular board");
19             for (char c : row) if (c < 'a' || c > 'z') throw new IllegalArgumentException("invalid board letter");
20         }
21         for (String word : words) {
22             Objects.requireNonNull(word,"word");
23             if (word.isEmpty()) throw new IllegalArgumentException("empty dictionary word");
24             for (int i=0;i<word.length();i++) if (word.charAt(i) < 'a' || word.charAt(i) > 'z') throw new IllegalArgumentException("invalid dictionary letter");
25         }
26         return columns;
27     }
28     private static void enter(int row, int column, Node node, boolean[][] used, ArrayDeque<Frame> stack, List<String> result) {
29         used[row][column] = true;
30         stack.push(new Frame(row,column,node));
31         if (node.word != null) { result.add(node.word); node.word = null; }
32     }
33     public static List<String> findWords(char[][] board, String[] words) {
34         int columns = validate(board,words);
35         List<String> result = new ArrayList<>();
36         if (board.length == 0 || columns == 0 || words.length == 0) return result;
37         Node root = new Node();
38         for (String word : words) {
39             Node node = root;
40             for (int i=0;i<word.length();i++) {
41                 int slot = word.charAt(i)-'a';
42                 if (node.children[slot] == null) node.children[slot] = new Node();
43                 node = node.children[slot];
44             }
45             node.word = word;
46         }
47         boolean[][] used = new boolean[board.length][columns];
48         ArrayDeque<Frame> stack = new ArrayDeque<>();
49         for (int row=0;row<board.length;row++) for (int column=0;column<columns;column++) {
50             Node start = root.children[board[row][column]-'a'];
51             if (start == null) continue;
52             enter(row,column,start,used,stack,result);
53             while (!stack.isEmpty()) {
54                 Frame frame = stack.peek();
55                 if (frame.nextDirection == 4) { used[frame.row][frame.column] = false; stack.pop(); continue; }
56                 int direction = frame.nextDirection++;
57                 int nr = frame.row+DIRECTIONS[direction][0], nc = frame.column+DIRECTIONS[direction][1];
58                 if (nr < 0 || nr >= board.length || nc < 0 || nc >= columns || used[nr][nc]) continue;
59                 Node child = frame.node.children[board[nr][nc]-'a'];
60                 if (child == null) continue;
61                 enter(nr,nc,child,used,stack,result);
62             }
63         }
64         Collections.sort(result);
65         return result;
66     }
67     private static boolean visit(char[][] board, String word, int index, int row, int column, boolean[][] used) {
68         if (row < 0 || row >= board.length || column < 0 || column >= board[0].length || used[row][column] || board[row][column] != word.charAt(index)) return false;
69         if (index+1 == word.length()) return true;
70         used[row][column] = true;
71         boolean found = false;
72         for (int[] direction : DIRECTIONS) if (visit(board,word,index+1,row+direction[0],column+direction[1],used)) { found=true; break; }
73         used[row][column] = false;
74         return found;
75     }
76     public static List<String> baseline(char[][] board, String[] words) {
77         int columns = validate(board,words);
78         List<String> result = new ArrayList<>();
79         if (board.length == 0 || columns == 0) return result;
80         for (String word : new TreeSet<>(Arrays.asList(words))) {
81             boolean[][] used = new boolean[board.length][columns]; boolean found = false;
82             for (int row=0;row<board.length&&!found;row++) for (int column=0;column<columns;column++) if (visit(board,word,0,row,column,used)) { found=true; break; }
83             if (found) result.add(word);
84         }
85         return result;
86     }
87 }
88

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Validate all inputs before building or taking an empty-board return.
Board coordinates are separate from shared trie prefixes. The board never changes; used marks only the current simple path.
board
["aa"]
words
["a","aa","aaa","aa"]
paths
["","a","aa","aaa"]
remainingWords
["a","aa","aaa"]
found
[]
stack
[]
used
[[false,false]]
phase
"initial"
current
null
Enter one start cell and consume a terminal word at most once.
Clearing a local terminal deduplicates output; its child edges remain available for longer words.
board
["aa"]
words
["a","aa","aaa","aa"]
paths
["","a","aa","aaa"]
remainingWords
["aa","aaa"]
found
["a"]
stack
[{"row":0,"column":0,"prefix":"a","nextDirection":0}]
used
[[true,false]]
phase
"enter-start"
current
[0,0]
startIndex
0
matched
"a"
Reject one neighbor while preserving the current path.
Direction order is up, right, down, left. A used coordinate cannot be reused, even if its letter would extend a trie path.
board
["aa"]
words
["a","aa","aaa","aa"]
paths
["","a","aa","aaa"]
remainingWords
["aa","aaa"]
found
["a"]
stack
[{"row":0,"column":0,"prefix":"a","nextDirection":1}]
used
[[true,false]]
phase
"skip"
current
[0,0]
probe
[-1,0]
direction
0
reason
"outside"
Extend the simple path along an existing trie edge.
A shared trie node may be reached by many board paths. Only its local terminal is cleared after the first emitted occurrence.
board
["aa"]
words
["a","aa","aaa","aa"]
paths
["","a","aa","aaa"]
remainingWords
["aaa"]
found
["a","aa"]
stack
[{"row":0,"column":0,"prefix":"a","nextDirection":2},{"row":0,"column":1,"prefix":"aa","nextDirection":0}]
used
[[true,true]]
phase
"enter"
current
[0,1]
direction
1
matched
"aa"
Reject one neighbor while preserving the current path.
Direction order is up, right, down, left. A used coordinate cannot be reused, even if its letter would extend a trie path.
board
["aa"]
words
["a","aa","aaa","aa"]
paths
["","a","aa","aaa"]
remainingWords
["aaa"]
found
["a","aa"]
stack
[{"row":0,"column":0,"prefix":"a","nextDirection":2},{"row":0,"column":1,"prefix":"aa","nextDirection":1}]
used
[[true,true]]
phase
"skip"
current
[0,1]
probe
[-1,1]
direction
0
reason
"outside"
Reject one neighbor while preserving the current path.
Direction order is up, right, down, left. A used coordinate cannot be reused, even if its letter would extend a trie path.
board
["aa"]
words
["a","aa","aaa","aa"]
paths
["","a","aa","aaa"]
remainingWords
["aaa"]
found
["a","aa"]
stack
[{"row":0,"column":0,"prefix":"a","nextDirection":2},{"row":0,"column":1,"prefix":"aa","nextDirection":2}]
used
[[true,true]]
phase
"skip"
current
[0,1]
probe
[0,2]
direction
1
reason
"outside"
Reject one neighbor while preserving the current path.
Direction order is up, right, down, left. A used coordinate cannot be reused, even if its letter would extend a trie path.
board
["aa"]
words
["a","aa","aaa","aa"]
paths
["","a","aa","aaa"]
remainingWords
["aaa"]
found
["a","aa"]
stack
[{"row":0,"column":0,"prefix":"a","nextDirection":2},{"row":0,"column":1,"prefix":"aa","nextDirection":3}]
used
[[true,true]]
phase
"skip"
current
[0,1]
probe
[1,1]
direction
2
reason
"outside"
Reject one neighbor while preserving the current path.
Direction order is up, right, down, left. A used coordinate cannot be reused, even if its letter would extend a trie path.
board
["aa"]
words
["a","aa","aaa","aa"]
paths
["","a","aa","aaa"]
remainingWords
["aaa"]
found
["a","aa"]
stack
[{"row":0,"column":0,"prefix":"a","nextDirection":2},{"row":0,"column":1,"prefix":"aa","nextDirection":4}]
used
[[true,true]]
phase
"skip"
current
[0,1]
probe
[0,0]
direction
3
reason
"used"
Backtrack after all four directions and release this coordinate.
The used matrix equals exactly the coordinates still on the stack. This cell may be reused by another path.
board
["aa"]
words
["a","aa","aaa","aa"]
paths
["","a","aa","aaa"]
remainingWords
["aaa"]
found
["a","aa"]
stack
[{"row":0,"column":0,"prefix":"a","nextDirection":2}]
used
[[true,false]]
phase
"backtrack"
current
[0,1]
Reject one neighbor while preserving the current path.
Direction order is up, right, down, left. A used coordinate cannot be reused, even if its letter would extend a trie path.
board
["aa"]
words
["a","aa","aaa","aa"]
paths
["","a","aa","aaa"]
remainingWords
["aaa"]
found
["a","aa"]
stack
[{"row":0,"column":0,"prefix":"a","nextDirection":3}]
used
[[true,false]]
phase
"skip"
current
[0,0]
probe
[1,0]
direction
2
reason
"outside"
Reject one neighbor while preserving the current path.
Direction order is up, right, down, left. A used coordinate cannot be reused, even if its letter would extend a trie path.
board
["aa"]
words
["a","aa","aaa","aa"]
paths
["","a","aa","aaa"]
remainingWords
["aaa"]
found
["a","aa"]
stack
[{"row":0,"column":0,"prefix":"a","nextDirection":4}]
used
[[true,false]]
phase
"skip"
current
[0,0]
probe
[0,-1]
direction
3
reason
"outside"
Backtrack after all four directions and release this coordinate.
The used matrix equals exactly the coordinates still on the stack. This cell may be reused by another path.
board
["aa"]
words
["a","aa","aaa","aa"]
paths
["","a","aa","aaa"]
remainingWords
["aaa"]
found
["a","aa"]
stack
[]
used
[[false,false]]
phase
"backtrack"
current
[0,0]
Enter one start cell and consume a terminal word at most once.
Clearing a local terminal deduplicates output; its child edges remain available for longer words.
board
["aa"]
words
["a","aa","aaa","aa"]
paths
["","a","aa","aaa"]
remainingWords
["aaa"]
found
["a","aa"]
stack
[{"row":0,"column":1,"prefix":"a","nextDirection":0}]
used
[[false,true]]
phase
"enter-start"
current
[0,1]
startIndex
1
matched
null
Reject one neighbor while preserving the current path.
Direction order is up, right, down, left. A used coordinate cannot be reused, even if its letter would extend a trie path.
board
["aa"]
words
["a","aa","aaa","aa"]
paths
["","a","aa","aaa"]
remainingWords
["aaa"]
found
["a","aa"]
stack
[{"row":0,"column":1,"prefix":"a","nextDirection":1}]
used
[[false,true]]
phase
"skip"
current
[0,1]
probe
[-1,1]
direction
0
reason
"outside"
Reject one neighbor while preserving the current path.
Direction order is up, right, down, left. A used coordinate cannot be reused, even if its letter would extend a trie path.
board
["aa"]
words
["a","aa","aaa","aa"]
paths
["","a","aa","aaa"]
remainingWords
["aaa"]
found
["a","aa"]
stack
[{"row":0,"column":1,"prefix":"a","nextDirection":2}]
used
[[false,true]]
phase
"skip"
current
[0,1]
probe
[0,2]
direction
1
reason
"outside"
Reject one neighbor while preserving the current path.
Direction order is up, right, down, left. A used coordinate cannot be reused, even if its letter would extend a trie path.
board
["aa"]
words
["a","aa","aaa","aa"]
paths
["","a","aa","aaa"]
remainingWords
["aaa"]
found
["a","aa"]
stack
[{"row":0,"column":1,"prefix":"a","nextDirection":3}]
used
[[false,true]]
phase
"skip"
current
[0,1]
probe
[1,1]
direction
2
reason
"outside"
Extend the simple path along an existing trie edge.
A shared trie node may be reached by many board paths. Only its local terminal is cleared after the first emitted occurrence.
board
["aa"]
words
["a","aa","aaa","aa"]
paths
["","a","aa","aaa"]
remainingWords
["aaa"]
found
["a","aa"]
stack
[{"row":0,"column":1,"prefix":"a","nextDirection":4},{"row":0,"column":0,"prefix":"aa","nextDirection":0}]
used
[[true,true]]
phase
"enter"
current
[0,0]
direction
3
matched
null
Reject one neighbor while preserving the current path.
Direction order is up, right, down, left. A used coordinate cannot be reused, even if its letter would extend a trie path.
board
["aa"]
words
["a","aa","aaa","aa"]
paths
["","a","aa","aaa"]
remainingWords
["aaa"]
found
["a","aa"]
stack
[{"row":0,"column":1,"prefix":"a","nextDirection":4},{"row":0,"column":0,"prefix":"aa","nextDirection":1}]
used
[[true,true]]
phase
"skip"
current
[0,0]
probe
[-1,0]
direction
0
reason
"outside"
Reject one neighbor while preserving the current path.
Direction order is up, right, down, left. A used coordinate cannot be reused, even if its letter would extend a trie path.
board
["aa"]
words
["a","aa","aaa","aa"]
paths
["","a","aa","aaa"]
remainingWords
["aaa"]
found
["a","aa"]
stack
[{"row":0,"column":1,"prefix":"a","nextDirection":4},{"row":0,"column":0,"prefix":"aa","nextDirection":2}]
used
[[true,true]]
phase
"skip"
current
[0,0]
probe
[0,1]
direction
1
reason
"used"
Reject one neighbor while preserving the current path.
Direction order is up, right, down, left. A used coordinate cannot be reused, even if its letter would extend a trie path.
board
["aa"]
words
["a","aa","aaa","aa"]
paths
["","a","aa","aaa"]
remainingWords
["aaa"]
found
["a","aa"]
stack
[{"row":0,"column":1,"prefix":"a","nextDirection":4},{"row":0,"column":0,"prefix":"aa","nextDirection":3}]
used
[[true,true]]
phase
"skip"
current
[0,0]
probe
[1,0]
direction
2
reason
"outside"
Reject one neighbor while preserving the current path.
Direction order is up, right, down, left. A used coordinate cannot be reused, even if its letter would extend a trie path.
board
["aa"]
words
["a","aa","aaa","aa"]
paths
["","a","aa","aaa"]
remainingWords
["aaa"]
found
["a","aa"]
stack
[{"row":0,"column":1,"prefix":"a","nextDirection":4},{"row":0,"column":0,"prefix":"aa","nextDirection":4}]
used
[[true,true]]
phase
"skip"
current
[0,0]
probe
[0,-1]
direction
3
reason
"outside"
Backtrack after all four directions and release this coordinate.
The used matrix equals exactly the coordinates still on the stack. This cell may be reused by another path.
board
["aa"]
words
["a","aa","aaa","aa"]
paths
["","a","aa","aaa"]
remainingWords
["aaa"]
found
["a","aa"]
stack
[{"row":0,"column":1,"prefix":"a","nextDirection":4}]
used
[[false,true]]
phase
"backtrack"
current
[0,0]
Backtrack after all four directions and release this coordinate.
The used matrix equals exactly the coordinates still on the stack. This cell may be reused by another path.
board
["aa"]
words
["a","aa","aaa","aa"]
paths
["","a","aa","aaa"]
remainingWords
["aaa"]
found
["a","aa"]
stack
[]
used
[[false,false]]
phase
"backtrack"
current
[0,1]
Sort the distinct found words for a deterministic API result.
Every start path is exhausted and all used flags are false. Terminal clearing is call-local; a later findWords call builds a fresh trie.
board
["aa"]
words
["a","aa","aaa","aa"]
paths
["","a","aa","aaa"]
remainingWords
["aaa"]
found
["a","aa"]
stack
[]
used
[[false,false]]
phase
"sorted"
current
null
Return the documented operation outcomes, unique found words, or exact replacement text.
Trie path displays are logical views. Board-path visited state and terminal flags have different lifetimes; no caller-owned input is mutated.
result
["a","aa"]

Diagonal contact is not adjacency

Input: {"board":["ab","cd"],"words":["ad","ac","bd"]} · Unique sorted found words: ["ac","bd"]

Step 1 of 27: Validate all inputs before building or taking an empty-board return.

Board coordinates are separate from shared trie prefixes. The board never changes; used marks only the current simple path.

Board search — trie prefixes and path-local coordinate ownership

Phase: initial.

Trie paths — sorted logical display

(root / empty path)prefix path only
aprefix path only
acterminal word
adterminal word
bprefix path only
bdterminal word

✓ means this coordinate belongs to the current path. The source letters never change.

Path continuations — stack top at right

Empty.

Words found so far — discovery order

Empty.

Path cards represent shared dictionary prefixes, not board cells or dictionary occurrence order. Complete exact state and equivalent static steps remain available below.

State after this step
Variable	Value
board	`["ab","cd"]`
words	`["ad","ac","bd"]`
paths	`["","a","ac","ad","b","bd"]`
remainingWords	`["ac","ad","bd"]`
found	`[]`
stack	`[]`
used	`[[false,false],[false,false]]`
phase	`"initial"`
current	`null`

See the affected Java block

 1 import java.util.*;
 2 public final class Solution {
 3     private static final int[][] DIRECTIONS = {{-1,0},{0,1},{1,0},{0,-1}};
 4     private static final class Node {
 5         final Node[] children = new Node[26];
 6         String word;
 7     }
 8     private static final class Frame {
 9         final int row, column;
10         final Node node;
11         int nextDirection;
12         Frame(int row, int column, Node node) { this.row=row; this.column=column; this.node=node; }
13     }
14     private static int validate(char[][] board, String[] words) {
15         Objects.requireNonNull(board,"board"); Objects.requireNonNull(words,"words");
16         int columns = board.length == 0 ? 0 : board[0] == null ? -1 : board[0].length;
17         for (char[] row : board) {
18             if (row == null || row.length != columns) throw new IllegalArgumentException("nonrectangular board");
19             for (char c : row) if (c < 'a' || c > 'z') throw new IllegalArgumentException("invalid board letter");
20         }
21         for (String word : words) {
22             Objects.requireNonNull(word,"word");
23             if (word.isEmpty()) throw new IllegalArgumentException("empty dictionary word");
24             for (int i=0;i<word.length();i++) if (word.charAt(i) < 'a' || word.charAt(i) > 'z') throw new IllegalArgumentException("invalid dictionary letter");
25         }
26         return columns;
27     }
28     private static void enter(int row, int column, Node node, boolean[][] used, ArrayDeque<Frame> stack, List<String> result) {
29         used[row][column] = true;
30         stack.push(new Frame(row,column,node));
31         if (node.word != null) { result.add(node.word); node.word = null; }
32     }
33     public static List<String> findWords(char[][] board, String[] words) {
34         int columns = validate(board,words);
35         List<String> result = new ArrayList<>();
36         if (board.length == 0 || columns == 0 || words.length == 0) return result;
37         Node root = new Node();
38         for (String word : words) {
39             Node node = root;
40             for (int i=0;i<word.length();i++) {
41                 int slot = word.charAt(i)-'a';
42                 if (node.children[slot] == null) node.children[slot] = new Node();
43                 node = node.children[slot];
44             }
45             node.word = word;
46         }
47         boolean[][] used = new boolean[board.length][columns];
48         ArrayDeque<Frame> stack = new ArrayDeque<>();
49         for (int row=0;row<board.length;row++) for (int column=0;column<columns;column++) {
50             Node start = root.children[board[row][column]-'a'];
51             if (start == null) continue;
52             enter(row,column,start,used,stack,result);
53             while (!stack.isEmpty()) {
54                 Frame frame = stack.peek();
55                 if (frame.nextDirection == 4) { used[frame.row][frame.column] = false; stack.pop(); continue; }
56                 int direction = frame.nextDirection++;
57                 int nr = frame.row+DIRECTIONS[direction][0], nc = frame.column+DIRECTIONS[direction][1];
58                 if (nr < 0 || nr >= board.length || nc < 0 || nc >= columns || used[nr][nc]) continue;
59                 Node child = frame.node.children[board[nr][nc]-'a'];
60                 if (child == null) continue;
61                 enter(nr,nc,child,used,stack,result);
62             }
63         }
64         Collections.sort(result);
65         return result;
66     }
67     private static boolean visit(char[][] board, String word, int index, int row, int column, boolean[][] used) {
68         if (row < 0 || row >= board.length || column < 0 || column >= board[0].length || used[row][column] || board[row][column] != word.charAt(index)) return false;
69         if (index+1 == word.length()) return true;
70         used[row][column] = true;
71         boolean found = false;
72         for (int[] direction : DIRECTIONS) if (visit(board,word,index+1,row+direction[0],column+direction[1],used)) { found=true; break; }
73         used[row][column] = false;
74         return found;
75     }
76     public static List<String> baseline(char[][] board, String[] words) {
77         int columns = validate(board,words);
78         List<String> result = new ArrayList<>();
79         if (board.length == 0 || columns == 0) return result;
80         for (String word : new TreeSet<>(Arrays.asList(words))) {
81             boolean[][] used = new boolean[board.length][columns]; boolean found = false;
82             for (int row=0;row<board.length&&!found;row++) for (int column=0;column<columns;column++) if (visit(board,word,0,row,column,used)) { found=true; break; }
83             if (found) result.add(word);
84         }
85         return result;
86     }
87 }
88

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Validate all inputs before building or taking an empty-board return.
Board coordinates are separate from shared trie prefixes. The board never changes; used marks only the current simple path.
board
["ab","cd"]
words
["ad","ac","bd"]
paths
["","a","ac","ad","b","bd"]
remainingWords
["ac","ad","bd"]
found
[]
stack
[]
used
[[false,false],[false,false]]
phase
"initial"
current
null
Enter one start cell and consume a terminal word at most once.
Clearing a local terminal deduplicates output; its child edges remain available for longer words.
board
["ab","cd"]
words
["ad","ac","bd"]
paths
["","a","ac","ad","b","bd"]
remainingWords
["ac","ad","bd"]
found
[]
stack
[{"row":0,"column":0,"prefix":"a","nextDirection":0}]
used
[[true,false],[false,false]]
phase
"enter-start"
current
[0,0]
startIndex
0
matched
null
Reject one neighbor while preserving the current path.
Direction order is up, right, down, left. A used coordinate cannot be reused, even if its letter would extend a trie path.
board
["ab","cd"]
words
["ad","ac","bd"]
paths
["","a","ac","ad","b","bd"]
remainingWords
["ac","ad","bd"]
found
[]
stack
[{"row":0,"column":0,"prefix":"a","nextDirection":1}]
used
[[true,false],[false,false]]
phase
"skip"
current
[0,0]
probe
[-1,0]
direction
0
reason
"outside"
Reject one neighbor while preserving the current path.
Direction order is up, right, down, left. A used coordinate cannot be reused, even if its letter would extend a trie path.
board
["ab","cd"]
words
["ad","ac","bd"]
paths
["","a","ac","ad","b","bd"]
remainingWords
["ac","ad","bd"]
found
[]
stack
[{"row":0,"column":0,"prefix":"a","nextDirection":2}]
used
[[true,false],[false,false]]
phase
"skip"
current
[0,0]
probe
[0,1]
direction
1
reason
"no-prefix"
Extend the simple path along an existing trie edge.
A shared trie node may be reached by many board paths. Only its local terminal is cleared after the first emitted occurrence.
board
["ab","cd"]
words
["ad","ac","bd"]
paths
["","a","ac","ad","b","bd"]
remainingWords
["ad","bd"]
found
["ac"]
stack
[{"row":0,"column":0,"prefix":"a","nextDirection":3},{"row":1,"column":0,"prefix":"ac","nextDirection":0}]
used
[[true,false],[true,false]]
phase
"enter"
current
[1,0]
direction
2
matched
"ac"
Reject one neighbor while preserving the current path.
Direction order is up, right, down, left. A used coordinate cannot be reused, even if its letter would extend a trie path.
board
["ab","cd"]
words
["ad","ac","bd"]
paths
["","a","ac","ad","b","bd"]
remainingWords
["ad","bd"]
found
["ac"]
stack
[{"row":0,"column":0,"prefix":"a","nextDirection":3},{"row":1,"column":0,"prefix":"ac","nextDirection":1}]
used
[[true,false],[true,false]]
phase
"skip"
current
[1,0]
probe
[0,0]
direction
0
reason
"used"
Reject one neighbor while preserving the current path.
Direction order is up, right, down, left. A used coordinate cannot be reused, even if its letter would extend a trie path.
board
["ab","cd"]
words
["ad","ac","bd"]
paths
["","a","ac","ad","b","bd"]
remainingWords
["ad","bd"]
found
["ac"]
stack
[{"row":0,"column":0,"prefix":"a","nextDirection":3},{"row":1,"column":0,"prefix":"ac","nextDirection":2}]
used
[[true,false],[true,false]]
phase
"skip"
current
[1,0]
probe
[1,1]
direction
1
reason
"no-prefix"
Reject one neighbor while preserving the current path.
Direction order is up, right, down, left. A used coordinate cannot be reused, even if its letter would extend a trie path.
board
["ab","cd"]
words
["ad","ac","bd"]
paths
["","a","ac","ad","b","bd"]
remainingWords
["ad","bd"]
found
["ac"]
stack
[{"row":0,"column":0,"prefix":"a","nextDirection":3},{"row":1,"column":0,"prefix":"ac","nextDirection":3}]
used
[[true,false],[true,false]]
phase
"skip"
current
[1,0]
probe
[2,0]
direction
2
reason
"outside"
Reject one neighbor while preserving the current path.
Direction order is up, right, down, left. A used coordinate cannot be reused, even if its letter would extend a trie path.
board
["ab","cd"]
words
["ad","ac","bd"]
paths
["","a","ac","ad","b","bd"]
remainingWords
["ad","bd"]
found
["ac"]
stack
[{"row":0,"column":0,"prefix":"a","nextDirection":3},{"row":1,"column":0,"prefix":"ac","nextDirection":4}]
used
[[true,false],[true,false]]
phase
"skip"
current
[1,0]
probe
[1,-1]
direction
3
reason
"outside"
Backtrack after all four directions and release this coordinate.
The used matrix equals exactly the coordinates still on the stack. This cell may be reused by another path.
board
["ab","cd"]
words
["ad","ac","bd"]
paths
["","a","ac","ad","b","bd"]
remainingWords
["ad","bd"]
found
["ac"]
stack
[{"row":0,"column":0,"prefix":"a","nextDirection":3}]
used
[[true,false],[false,false]]
phase
"backtrack"
current
[1,0]
Reject one neighbor while preserving the current path.
Direction order is up, right, down, left. A used coordinate cannot be reused, even if its letter would extend a trie path.
board
["ab","cd"]
words
["ad","ac","bd"]
paths
["","a","ac","ad","b","bd"]
remainingWords
["ad","bd"]
found
["ac"]
stack
[{"row":0,"column":0,"prefix":"a","nextDirection":4}]
used
[[true,false],[false,false]]
phase
"skip"
current
[0,0]
probe
[0,-1]
direction
3
reason
"outside"
Backtrack after all four directions and release this coordinate.
The used matrix equals exactly the coordinates still on the stack. This cell may be reused by another path.
board
["ab","cd"]
words
["ad","ac","bd"]
paths
["","a","ac","ad","b","bd"]
remainingWords
["ad","bd"]
found
["ac"]
stack
[]
used
[[false,false],[false,false]]
phase
"backtrack"
current
[0,0]
Enter one start cell and consume a terminal word at most once.
Clearing a local terminal deduplicates output; its child edges remain available for longer words.
board
["ab","cd"]
words
["ad","ac","bd"]
paths
["","a","ac","ad","b","bd"]
remainingWords
["ad","bd"]
found
["ac"]
stack
[{"row":0,"column":1,"prefix":"b","nextDirection":0}]
used
[[false,true],[false,false]]
phase
"enter-start"
current
[0,1]
startIndex
1
matched
null
Reject one neighbor while preserving the current path.
Direction order is up, right, down, left. A used coordinate cannot be reused, even if its letter would extend a trie path.
board
["ab","cd"]
words
["ad","ac","bd"]
paths
["","a","ac","ad","b","bd"]
remainingWords
["ad","bd"]
found
["ac"]
stack
[{"row":0,"column":1,"prefix":"b","nextDirection":1}]
used
[[false,true],[false,false]]
phase
"skip"
current
[0,1]
probe
[-1,1]
direction
0
reason
"outside"
Reject one neighbor while preserving the current path.
Direction order is up, right, down, left. A used coordinate cannot be reused, even if its letter would extend a trie path.
board
["ab","cd"]
words
["ad","ac","bd"]
paths
["","a","ac","ad","b","bd"]
remainingWords
["ad","bd"]
found
["ac"]
stack
[{"row":0,"column":1,"prefix":"b","nextDirection":2}]
used
[[false,true],[false,false]]
phase
"skip"
current
[0,1]
probe
[0,2]
direction
1
reason
"outside"
Extend the simple path along an existing trie edge.
A shared trie node may be reached by many board paths. Only its local terminal is cleared after the first emitted occurrence.
board
["ab","cd"]
words
["ad","ac","bd"]
paths
["","a","ac","ad","b","bd"]
remainingWords
["ad"]
found
["ac","bd"]
stack
[{"row":0,"column":1,"prefix":"b","nextDirection":3},{"row":1,"column":1,"prefix":"bd","nextDirection":0}]
used
[[false,true],[false,true]]
phase
"enter"
current
[1,1]
direction
2
matched
"bd"
Reject one neighbor while preserving the current path.
Direction order is up, right, down, left. A used coordinate cannot be reused, even if its letter would extend a trie path.
board
["ab","cd"]
words
["ad","ac","bd"]
paths
["","a","ac","ad","b","bd"]
remainingWords
["ad"]
found
["ac","bd"]
stack
[{"row":0,"column":1,"prefix":"b","nextDirection":3},{"row":1,"column":1,"prefix":"bd","nextDirection":1}]
used
[[false,true],[false,true]]
phase
"skip"
current
[1,1]
probe
[0,1]
direction
0
reason
"used"
Reject one neighbor while preserving the current path.
Direction order is up, right, down, left. A used coordinate cannot be reused, even if its letter would extend a trie path.
board
["ab","cd"]
words
["ad","ac","bd"]
paths
["","a","ac","ad","b","bd"]
remainingWords
["ad"]
found
["ac","bd"]
stack
[{"row":0,"column":1,"prefix":"b","nextDirection":3},{"row":1,"column":1,"prefix":"bd","nextDirection":2}]
used
[[false,true],[false,true]]
phase
"skip"
current
[1,1]
probe
[1,2]
direction
1
reason
"outside"
Reject one neighbor while preserving the current path.
Direction order is up, right, down, left. A used coordinate cannot be reused, even if its letter would extend a trie path.
board
["ab","cd"]
words
["ad","ac","bd"]
paths
["","a","ac","ad","b","bd"]
remainingWords
["ad"]
found
["ac","bd"]
stack
[{"row":0,"column":1,"prefix":"b","nextDirection":3},{"row":1,"column":1,"prefix":"bd","nextDirection":3}]
used
[[false,true],[false,true]]
phase
"skip"
current
[1,1]
probe
[2,1]
direction
2
reason
"outside"
Reject one neighbor while preserving the current path.
Direction order is up, right, down, left. A used coordinate cannot be reused, even if its letter would extend a trie path.
board
["ab","cd"]
words
["ad","ac","bd"]
paths
["","a","ac","ad","b","bd"]
remainingWords
["ad"]
found
["ac","bd"]
stack
[{"row":0,"column":1,"prefix":"b","nextDirection":3},{"row":1,"column":1,"prefix":"bd","nextDirection":4}]
used
[[false,true],[false,true]]
phase
"skip"
current
[1,1]
probe
[1,0]
direction
3
reason
"no-prefix"
Backtrack after all four directions and release this coordinate.
The used matrix equals exactly the coordinates still on the stack. This cell may be reused by another path.
board
["ab","cd"]
words
["ad","ac","bd"]
paths
["","a","ac","ad","b","bd"]
remainingWords
["ad"]
found
["ac","bd"]
stack
[{"row":0,"column":1,"prefix":"b","nextDirection":3}]
used
[[false,true],[false,false]]
phase
"backtrack"
current
[1,1]
Reject one neighbor while preserving the current path.
Direction order is up, right, down, left. A used coordinate cannot be reused, even if its letter would extend a trie path.
board
["ab","cd"]
words
["ad","ac","bd"]
paths
["","a","ac","ad","b","bd"]
remainingWords
["ad"]
found
["ac","bd"]
stack
[{"row":0,"column":1,"prefix":"b","nextDirection":4}]
used
[[false,true],[false,false]]
phase
"skip"
current
[0,1]
probe
[0,0]
direction
3
reason
"no-prefix"
Backtrack after all four directions and release this coordinate.
The used matrix equals exactly the coordinates still on the stack. This cell may be reused by another path.
board
["ab","cd"]
words
["ad","ac","bd"]
paths
["","a","ac","ad","b","bd"]
remainingWords
["ad"]
found
["ac","bd"]
stack
[]
used
[[false,false],[false,false]]
phase
"backtrack"
current
[0,1]
Skip a start cell with no root trie edge.
A dictionary word cannot begin at this cell, but later starts are still considered.
board
["ab","cd"]
words
["ad","ac","bd"]
paths
["","a","ac","ad","b","bd"]
remainingWords
["ad"]
found
["ac","bd"]
stack
[]
used
[[false,false],[false,false]]
phase
"start-missing"
current
[1,0]
startIndex
2
Skip a start cell with no root trie edge.
A dictionary word cannot begin at this cell, but later starts are still considered.
board
["ab","cd"]
words
["ad","ac","bd"]
paths
["","a","ac","ad","b","bd"]
remainingWords
["ad"]
found
["ac","bd"]
stack
[]
used
[[false,false],[false,false]]
phase
"start-missing"
current
[1,1]
startIndex
3
Sort the distinct found words for a deterministic API result.
Every start path is exhausted and all used flags are false. Terminal clearing is call-local; a later findWords call builds a fresh trie.
board
["ab","cd"]
words
["ad","ac","bd"]
paths
["","a","ac","ad","b","bd"]
remainingWords
["ad"]
found
["ac","bd"]
stack
[]
used
[[false,false],[false,false]]
phase
"sorted"
current
null
Return the documented operation outcomes, unique found words, or exact replacement text.
Trie path displays are logical views. Board-path visited state and terminal flags have different lifetimes; no caller-owned input is mutated.
result
["ac","bd"]

Empty board with valid dictionary

Input: {"board":[],"words":["a"]} · Unique sorted found words: []

Step 1 of 2: Validate all inputs before building or taking an empty-board return.

Board coordinates are separate from shared trie prefixes. The board never changes; used marks only the current simple path.

Board search — trie prefixes and path-local coordinate ownership

Phase: initial.

Trie paths — sorted logical display

No trie was built for this empty-input return.

✓ means this coordinate belongs to the current path. The source letters never change.

Path continuations — stack top at right

Empty.

Words found so far — discovery order

Empty.

Path cards represent shared dictionary prefixes, not board cells or dictionary occurrence order. Complete exact state and equivalent static steps remain available below.

State after this step
Variable	Value
board	`[]`
words	`["a"]`
paths	`[]`
remainingWords	`[]`
found	`[]`
stack	`[]`
used	`[]`
phase	`"initial"`
current	`null`

See the affected Java block

 1 import java.util.*;
 2 public final class Solution {
 3     private static final int[][] DIRECTIONS = {{-1,0},{0,1},{1,0},{0,-1}};
 4     private static final class Node {
 5         final Node[] children = new Node[26];
 6         String word;
 7     }
 8     private static final class Frame {
 9         final int row, column;
10         final Node node;
11         int nextDirection;
12         Frame(int row, int column, Node node) { this.row=row; this.column=column; this.node=node; }
13     }
14     private static int validate(char[][] board, String[] words) {
15         Objects.requireNonNull(board,"board"); Objects.requireNonNull(words,"words");
16         int columns = board.length == 0 ? 0 : board[0] == null ? -1 : board[0].length;
17         for (char[] row : board) {
18             if (row == null || row.length != columns) throw new IllegalArgumentException("nonrectangular board");
19             for (char c : row) if (c < 'a' || c > 'z') throw new IllegalArgumentException("invalid board letter");
20         }
21         for (String word : words) {
22             Objects.requireNonNull(word,"word");
23             if (word.isEmpty()) throw new IllegalArgumentException("empty dictionary word");
24             for (int i=0;i<word.length();i++) if (word.charAt(i) < 'a' || word.charAt(i) > 'z') throw new IllegalArgumentException("invalid dictionary letter");
25         }
26         return columns;
27     }
28     private static void enter(int row, int column, Node node, boolean[][] used, ArrayDeque<Frame> stack, List<String> result) {
29         used[row][column] = true;
30         stack.push(new Frame(row,column,node));
31         if (node.word != null) { result.add(node.word); node.word = null; }
32     }
33     public static List<String> findWords(char[][] board, String[] words) {
34         int columns = validate(board,words);
35         List<String> result = new ArrayList<>();
36         if (board.length == 0 || columns == 0 || words.length == 0) return result;
37         Node root = new Node();
38         for (String word : words) {
39             Node node = root;
40             for (int i=0;i<word.length();i++) {
41                 int slot = word.charAt(i)-'a';
42                 if (node.children[slot] == null) node.children[slot] = new Node();
43                 node = node.children[slot];
44             }
45             node.word = word;
46         }
47         boolean[][] used = new boolean[board.length][columns];
48         ArrayDeque<Frame> stack = new ArrayDeque<>();
49         for (int row=0;row<board.length;row++) for (int column=0;column<columns;column++) {
50             Node start = root.children[board[row][column]-'a'];
51             if (start == null) continue;
52             enter(row,column,start,used,stack,result);
53             while (!stack.isEmpty()) {
54                 Frame frame = stack.peek();
55                 if (frame.nextDirection == 4) { used[frame.row][frame.column] = false; stack.pop(); continue; }
56                 int direction = frame.nextDirection++;
57                 int nr = frame.row+DIRECTIONS[direction][0], nc = frame.column+DIRECTIONS[direction][1];
58                 if (nr < 0 || nr >= board.length || nc < 0 || nc >= columns || used[nr][nc]) continue;
59                 Node child = frame.node.children[board[nr][nc]-'a'];
60                 if (child == null) continue;
61                 enter(nr,nc,child,used,stack,result);
62             }
63         }
64         Collections.sort(result);
65         return result;
66     }
67     private static boolean visit(char[][] board, String word, int index, int row, int column, boolean[][] used) {
68         if (row < 0 || row >= board.length || column < 0 || column >= board[0].length || used[row][column] || board[row][column] != word.charAt(index)) return false;
69         if (index+1 == word.length()) return true;
70         used[row][column] = true;
71         boolean found = false;
72         for (int[] direction : DIRECTIONS) if (visit(board,word,index+1,row+direction[0],column+direction[1],used)) { found=true; break; }
73         used[row][column] = false;
74         return found;
75     }
76     public static List<String> baseline(char[][] board, String[] words) {
77         int columns = validate(board,words);
78         List<String> result = new ArrayList<>();
79         if (board.length == 0 || columns == 0) return result;
80         for (String word : new TreeSet<>(Arrays.asList(words))) {
81             boolean[][] used = new boolean[board.length][columns]; boolean found = false;
82             for (int row=0;row<board.length&&!found;row++) for (int column=0;column<columns;column++) if (visit(board,word,0,row,column,used)) { found=true; break; }
83             if (found) result.add(word);
84         }
85         return result;
86     }
87 }
88

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Validate all inputs before building or taking an empty-board return.
Board coordinates are separate from shared trie prefixes. The board never changes; used marks only the current simple path.
board
[]
words
["a"]
paths
[]
remainingWords
[]
found
[]
stack
[]
used
[]
phase
"initial"
current
null
Return the documented operation outcomes, unique found words, or exact replacement text.
Trie path displays are logical views. Board-path visited state and terminal flags have different lifetimes; no caller-owned input is mutated.
result
[]

Empty dictionary returns fresh empty output

Input: {"board":["ab"],"words":[]} · Unique sorted found words: []

Step 1 of 2: Validate all inputs before building or taking an empty-board return.

Board coordinates are separate from shared trie prefixes. The board never changes; used marks only the current simple path.

Board search — trie prefixes and path-local coordinate ownership

Phase: initial.

Trie paths — sorted logical display

No trie was built for this empty-input return.

✓ means this coordinate belongs to the current path. The source letters never change.

Path continuations — stack top at right

Empty.

Words found so far — discovery order

Empty.

Path cards represent shared dictionary prefixes, not board cells or dictionary occurrence order. Complete exact state and equivalent static steps remain available below.

State after this step
Variable	Value
board	`["ab"]`
words	`[]`
paths	`[]`
remainingWords	`[]`
found	`[]`
stack	`[]`
used	`[]`
phase	`"initial"`
current	`null`

See the affected Java block

 1 import java.util.*;
 2 public final class Solution {
 3     private static final int[][] DIRECTIONS = {{-1,0},{0,1},{1,0},{0,-1}};
 4     private static final class Node {
 5         final Node[] children = new Node[26];
 6         String word;
 7     }
 8     private static final class Frame {
 9         final int row, column;
10         final Node node;
11         int nextDirection;
12         Frame(int row, int column, Node node) { this.row=row; this.column=column; this.node=node; }
13     }
14     private static int validate(char[][] board, String[] words) {
15         Objects.requireNonNull(board,"board"); Objects.requireNonNull(words,"words");
16         int columns = board.length == 0 ? 0 : board[0] == null ? -1 : board[0].length;
17         for (char[] row : board) {
18             if (row == null || row.length != columns) throw new IllegalArgumentException("nonrectangular board");
19             for (char c : row) if (c < 'a' || c > 'z') throw new IllegalArgumentException("invalid board letter");
20         }
21         for (String word : words) {
22             Objects.requireNonNull(word,"word");
23             if (word.isEmpty()) throw new IllegalArgumentException("empty dictionary word");
24             for (int i=0;i<word.length();i++) if (word.charAt(i) < 'a' || word.charAt(i) > 'z') throw new IllegalArgumentException("invalid dictionary letter");
25         }
26         return columns;
27     }
28     private static void enter(int row, int column, Node node, boolean[][] used, ArrayDeque<Frame> stack, List<String> result) {
29         used[row][column] = true;
30         stack.push(new Frame(row,column,node));
31         if (node.word != null) { result.add(node.word); node.word = null; }
32     }
33     public static List<String> findWords(char[][] board, String[] words) {
34         int columns = validate(board,words);
35         List<String> result = new ArrayList<>();
36         if (board.length == 0 || columns == 0 || words.length == 0) return result;
37         Node root = new Node();
38         for (String word : words) {
39             Node node = root;
40             for (int i=0;i<word.length();i++) {
41                 int slot = word.charAt(i)-'a';
42                 if (node.children[slot] == null) node.children[slot] = new Node();
43                 node = node.children[slot];
44             }
45             node.word = word;
46         }
47         boolean[][] used = new boolean[board.length][columns];
48         ArrayDeque<Frame> stack = new ArrayDeque<>();
49         for (int row=0;row<board.length;row++) for (int column=0;column<columns;column++) {
50             Node start = root.children[board[row][column]-'a'];
51             if (start == null) continue;
52             enter(row,column,start,used,stack,result);
53             while (!stack.isEmpty()) {
54                 Frame frame = stack.peek();
55                 if (frame.nextDirection == 4) { used[frame.row][frame.column] = false; stack.pop(); continue; }
56                 int direction = frame.nextDirection++;
57                 int nr = frame.row+DIRECTIONS[direction][0], nc = frame.column+DIRECTIONS[direction][1];
58                 if (nr < 0 || nr >= board.length || nc < 0 || nc >= columns || used[nr][nc]) continue;
59                 Node child = frame.node.children[board[nr][nc]-'a'];
60                 if (child == null) continue;
61                 enter(nr,nc,child,used,stack,result);
62             }
63         }
64         Collections.sort(result);
65         return result;
66     }
67     private static boolean visit(char[][] board, String word, int index, int row, int column, boolean[][] used) {
68         if (row < 0 || row >= board.length || column < 0 || column >= board[0].length || used[row][column] || board[row][column] != word.charAt(index)) return false;
69         if (index+1 == word.length()) return true;
70         used[row][column] = true;
71         boolean found = false;
72         for (int[] direction : DIRECTIONS) if (visit(board,word,index+1,row+direction[0],column+direction[1],used)) { found=true; break; }
73         used[row][column] = false;
74         return found;
75     }
76     public static List<String> baseline(char[][] board, String[] words) {
77         int columns = validate(board,words);
78         List<String> result = new ArrayList<>();
79         if (board.length == 0 || columns == 0) return result;
80         for (String word : new TreeSet<>(Arrays.asList(words))) {
81             boolean[][] used = new boolean[board.length][columns]; boolean found = false;
82             for (int row=0;row<board.length&&!found;row++) for (int column=0;column<columns;column++) if (visit(board,word,0,row,column,used)) { found=true; break; }
83             if (found) result.add(word);
84         }
85         return result;
86     }
87 }
88

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Validate all inputs before building or taking an empty-board return.
Board coordinates are separate from shared trie prefixes. The board never changes; used marks only the current simple path.
board
["ab"]
words
[]
paths
[]
remainingWords
[]
found
[]
stack
[]
used
[]
phase
"initial"
current
null
Return the documented operation outcomes, unique found words, or exact replacement text.
Trie path displays are logical views. Board-path visited state and terminal flags have different lifetimes; no caller-owned input is mutated.
result
[]

Test the contract

Input: Empty board or zero columns; valid words
Output: []
Validation still checks the complete inputs.
Input: Duplicate dictionary word found by multiple paths
Output: one sorted occurrence
Call-local terminal consumption.
Input: A word that needs a diagonal or reused coordinate
Output: absent
Exact path contract.
Input: Shared board rows
Output: same words as coordinate-equivalent independent rows
No marker writes to aliased source rows.
Input: 12×12 forced snake spelling 144 letters
Output: long word and its prefix found
Full path depth and continuation restoration.

Common mistakes and counterexamples

Leave a cell globally visited

Counterexample: Another word or start may legitimately use that coordinate.

Unmark exactly when its frame backtracks.

Clear a found node’s child edges

Counterexample: Finding o must not delete the path needed for oa or oath.

Clear only the complete-word terminal, retaining descendants.

Return duplicates from repeated words or paths

Counterexample: Two paths spelling aa do not represent two dictionary results.

Consume each call-local terminal once, then sort.

Write markers into the board

Counterexample: Shared row arrays can make a write affect another coordinate and violate preservation.

Use an independent coordinate-indexed used matrix.

Follow-ups

Return one coordinate path per word.

Copy or reconstruct the current stack when its terminal is first emitted. Define a deterministic witness order and count total path-copy output cost.

Prune exhausted trie branches.

Maintain remaining-terminal counts or carefully delete a child only when its whole subtree has no unreported word. Prove that global dictionary pruning is safe even though board used state is path-local.

Search the same dictionary on many boards.

Persistent terminal clearing would corrupt later searches. Keep immutable terminal metadata plus a per-board found set, or rebuild/copy the relevant trie state with explicit preprocessing and query costs.

Related foundations

Keep practicing

Return to the lesson

AceYourInterviews · 2026-10-17 · Original teaching content and implementations authored for AceYourInterviews. Standard names do not imply company-frequency or external-platform equivalence claims.