DSA-124 · Coordinate backtracking with explicit suspended direction frames

Word Search — Single Word

Advanced · Java 21 · Version 1 · editorial draft

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

Understand the problem

Return whether word can be spelled by an orthogonally adjacent path through board. Match one UTF-16 code unit per cell, preserve letter order, and never reuse a coordinate within that path.

board is a nonnull rectangular char[][] with nonnull rows; word is a nonnull String. Empty boards and zero-column rows are valid. Null outer board or word throws NullPointerException; null/ragged rows or more than 100,000 rows/cells throws IllegalArgumentException before any early return. All char values are valid; matching is exact and case-sensitive.
exists returns boolean. Empty word returns true for the empty path on any valid board, including no cells. A nonempty word longer than the cell count returns false. Moves are up/right/down/left only; repeated letters may use different coordinates, but one coordinate cannot be used twice in a candidate.
Preserve every board value and row reference on both success and failure. Shared source rows are allowed because vertices are coordinates. Private used marks and explicit frames are fully released before returning. Java chars and String.charAt operate on UTF-16 code units, so a supplementary Unicode character occupies two units rather than one grapheme cell.

Examples

Input: board=["ab","ca"], word="aba"
Output: true
Coordinates (0,0)→(0,1)→(1,1) spell the word without reuse.
Input: board=["ab","cd"], word="aba"
Output: false
Returning from b to the original a would reuse a coordinate.
Input: board=["ax","xb"], word="ab"
Output: false
The matching letters are diagonal, which is not a legal edge.
Input: board=[], word=""
Output: true
The empty path is a witness even without a start cell.

Before you start

Implicit orthogonal grid adjacency
Path-local ownership, prefix matching, and explicit recursion frames

Recognize the structure

A global visited set is wrong: failing one prefix must not forbid that coordinate in a different prefix or start. A state needs the active path’s used coordinates and the current word position. Matching the next character before descending prunes irrelevant paths. To support very long valid corridors, model the recursive continuation explicitly instead of relying on Java call depth.

Try before revealing

Hint 1

The same coordinate can be available in one branch and unavailable in another.

Hint 2

A frame needs its current cell, matched prefix index, and where to resume neighbor scanning.

Hint 3

Push only unused matching neighbors; pop and unmark exhausted frames, and unwind the successful path before returning.

Derive the solution

Reveal the baseline, optimized reasoning, and Java code

Enumerate coordinate-simple paths, then compare complete strings

For every start, recursively enumerate all orthogonal coordinate-simple paths of exactly word.length cells. Build their text and compare only at a complete leaf, rather than pruning on mismatched prefixes. Use private used marks and restore them on return. This compiling baseline is intentionally expensive and recursive; it is exercised only on bounded boards/words, not the 100,000-cell depth boundary.

Improve the baseline

Validate shapes and simple necessary conditions

Read all row shapes before checking an empty word. Then accept the empty path or reject length greater than the number of cells. For a nonempty viable length, allocate private coordinate marks and scan starts in row-major order, considering only matching first letters.

Store a suspended direction cursor in every frame

A frame holds vertex ID, matched word index, and the next direction to try. Mark a matching start and push its frame. Increment a frame’s direction cursor before exploring a neighbor, so the parent resumes at the following direction after the child returns. Claim only an unused coordinate matching the next code unit.

Backtrack on exhaustion and clean up on success

When all four directions fail, unmark that coordinate and pop its frame. If a frame matches the final word index, a witness exists; explicitly pop/unmark the whole successful path before returning true. Failed starts leave no marks, so later starts can use the whole board again.

Why it is correct

Active-path invariant

Frames from bottom to top describe a simple orthogonal path. Frame k has word index k and its coordinate contains word.charAt(k). used is true exactly for those frame coordinates. A legal matching child preserves these properties; failed-neighbor tests change only the direction cursor.

Complete exploration with restoration

Each frame tries all four directions exactly once unless a witness ends the search. An unused matching neighbor is the only possible next step of a valid witness. Exhaustion releases the current coordinate and restores its parent’s available choices, so every legal prefix and every matching start is considered without global visited leakage.

Correct return and bounded traversal

A final-index frame gives a complete matching simple path, proving true. If every start is exhausted, completeness rules out a witness, proving false. Path depth cannot exceed cell count or word length. Explicit frames implement this finite traversal without recursive stack overflow; cleanup changes no caller-owned values.

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 Frame {final int vertex,index;int direction;Frame(int vertex,int index){this.vertex=vertex;this.index=index;}}
    private static int columns(char[][] board,String word) {
        Objects.requireNonNull(board,"board");Objects.requireNonNull(word,"word");if(board.length>100000)throw new IllegalArgumentException("row limit");
        int cols=board.length==0?0:board[0]==null?-1:board[0].length;for(char[] row:board)if(row==null||row.length!=cols)throw new IllegalArgumentException("nonrectangular board");
        if((long)board.length*cols>100000)throw new IllegalArgumentException("cell limit");return cols;
    }
    public static boolean exists(char[][] board,String word) {
        int cols=columns(board,word),rows=board.length,cells=rows*cols;if(word.isEmpty())return true;if(word.length()>cells)return false;
        boolean[] used=new boolean[cells];ArrayDeque<Frame> stack=new ArrayDeque<>();
        for(int start=0;start<cells;start++)if(board[start/cols][start%cols]==word.charAt(0)) {
            used[start]=true;stack.push(new Frame(start,0));
            while(!stack.isEmpty()) {
                Frame current=stack.peek();
                if(current.index==word.length()-1) {
                    while(!stack.isEmpty())used[stack.pop().vertex]=false;
                    return true;
                }
                if(current.direction==4){used[current.vertex]=false;stack.pop();continue;}
                int[] direction=DIRECTIONS[current.direction++];int nr=current.vertex/cols+direction[0],nc=current.vertex%cols+direction[1];
                if(nr<0||nr>=rows||nc<0||nc>=cols)continue;int next=nr*cols+nc;
                if(used[next]||board[nr][nc]!=word.charAt(current.index+1))continue;
                used[next]=true;stack.push(new Frame(next,current.index+1));
            }
        }
        return false;
    }
    private static boolean enumerate(char[][] board,String word,int cols,int v,boolean[] used,StringBuilder path) {
        used[v]=true;path.append(board[v/cols][v%cols]);boolean found=false;
        if(path.length()==word.length())found=path.toString().equals(word);
        else for(int[] d:DIRECTIONS){int nr=v/cols+d[0],nc=v%cols+d[1];if(nr>=0&&nr<board.length&&nc>=0&&nc<cols&&!used[nr*cols+nc]&&enumerate(board,word,cols,nr*cols+nc,used,path)){found=true;break;}}
        path.setLength(path.length()-1);used[v]=false;return found;
    }
    public static boolean baseline(char[][] board,String word) {
        int cols=columns(board,word),cells=board.length*cols;if(word.isEmpty())return true;if(word.length()>cells)return false;
        boolean[] used=new boolean[cells];for(int v=0;v<cells;v++)if(enumerate(board,word,cols,v,used,new StringBuilder()))return true;return false;
    }
}

Read the meaningful blocks

Coordinate identity survives aliased rows

Two equal or shared char[] rows still occupy different row positions. Flat vertex=r*cols+c and a private boolean array distinguish those coordinates without writing a marker into the source. Such a marker would also need a collision policy because every char value is allowed.

Cursor movement is part of the continuation

The direction counter advances before a child is pushed. On child failure, popping it exposes a parent whose next direction is already correct. Reinitializing the cursor after return can repeat a branch forever or skip unexplored neighbors.

Success has an explicit cleanup path

Early success often bypasses recursive undo in mutable-board solutions. Here board is always read-only, and the private success loop additionally releases all path marks. The trace shows the matched witness before a sequence of unwind steps; the complete state has an empty stack and all-false used array.

Complexity

Let R be rows, B cells, and L the word length in UTF-16 units. Validation costs O(R+1). Empty-word and L>B shortcuts return after validation. Otherwise a safe loose main bound is O(R+B+B·4^L) time and O(B+L+1) auxiliary storage for private marks and explicit frames. Prefix mismatches and the no-reuse rule reduce actual work; the source board is not copied.

The baseline may enumerate the same geometric paths even when their first letter mismatches, then constructs/compares length-L text. A safe bound is O(R+B+B(L+1)4^L) time, with O(B+L+1) auxiliary marks, StringBuilder and recursive depth. Its recursion is unsuitable for the long-corridor test. Returning a boolean has constant output size; teaching histories and witness pictures are excluded from runtime workspace.

Exact-state walkthroughs

Reveal normal and boundary traces

A complete witness is followed by explicit cleanup

Input: {"board":["ab","ca"],"word":"aba"} · Matching coordinate path exists: true

Step 1 of 15: Validate the complete shape before empty-word or size shortcuts.

Board cells are read-only UTF-16 code units. Shared row objects still represent distinct coordinate vertices. Frames below are shown bottom-to-top, not ArrayDeque iterator order.

Word Search — active coordinates and suspended directions

Phase: initial.

Word: "aba". Match exact UTF-16 code units; moves are up, right, down, left.

Active path — bottom → top frames, in word order

Empty.

• means claimed by the active path. Board letters never change; coordinates remain distinct when source rows alias.

Explicit Java frames — bottom → top, with next direction cursors

Empty.

The Java implementation stores these frames explicitly. Choose, child entry/return, and undo are distinct steps. Full state tables and static traces appear below; teaching snapshots are excluded from Java workspace costs.

State after this step
Variable	Value
input	`{"board":["ab","ca"],"word":"aba"}`
rows	`2`
cols	`2`
used	`[false,false,false,false]`
frames	`[]`
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 Frame {final int vertex,index;int direction;Frame(int vertex,int index){this.vertex=vertex;this.index=index;}}
 5     private static int columns(char[][] board,String word) {
 6         Objects.requireNonNull(board,"board");Objects.requireNonNull(word,"word");if(board.length>100000)throw new IllegalArgumentException("row limit");
 7         int cols=board.length==0?0:board[0]==null?-1:board[0].length;for(char[] row:board)if(row==null||row.length!=cols)throw new IllegalArgumentException("nonrectangular board");
 8         if((long)board.length*cols>100000)throw new IllegalArgumentException("cell limit");return cols;
 9     }
10     public static boolean exists(char[][] board,String word) {
11         int cols=columns(board,word),rows=board.length,cells=rows*cols;if(word.isEmpty())return true;if(word.length()>cells)return false;
12         boolean[] used=new boolean[cells];ArrayDeque<Frame> stack=new ArrayDeque<>();
13         for(int start=0;start<cells;start++)if(board[start/cols][start%cols]==word.charAt(0)) {
14             used[start]=true;stack.push(new Frame(start,0));
15             while(!stack.isEmpty()) {
16                 Frame current=stack.peek();
17                 if(current.index==word.length()-1) {
18                     while(!stack.isEmpty())used[stack.pop().vertex]=false;
19                     return true;
20                 }
21                 if(current.direction==4){used[current.vertex]=false;stack.pop();continue;}
22                 int[] direction=DIRECTIONS[current.direction++];int nr=current.vertex/cols+direction[0],nc=current.vertex%cols+direction[1];
23                 if(nr<0||nr>=rows||nc<0||nc>=cols)continue;int next=nr*cols+nc;
24                 if(used[next]||board[nr][nc]!=word.charAt(current.index+1))continue;
25                 used[next]=true;stack.push(new Frame(next,current.index+1));
26             }
27         }
28         return false;
29     }
30     private static boolean enumerate(char[][] board,String word,int cols,int v,boolean[] used,StringBuilder path) {
31         used[v]=true;path.append(board[v/cols][v%cols]);boolean found=false;
32         if(path.length()==word.length())found=path.toString().equals(word);
33         else for(int[] d:DIRECTIONS){int nr=v/cols+d[0],nc=v%cols+d[1];if(nr>=0&&nr<board.length&&nc>=0&&nc<cols&&!used[nr*cols+nc]&&enumerate(board,word,cols,nr*cols+nc,used,path)){found=true;break;}}
34         path.setLength(path.length()-1);used[v]=false;return found;
35     }
36     public static boolean baseline(char[][] board,String word) {
37         int cols=columns(board,word),cells=board.length*cols;if(word.isEmpty())return true;if(word.length()>cells)return false;
38         boolean[] used=new boolean[cells];for(int v=0;v<cells;v++)if(enumerate(board,word,cols,v,used,new StringBuilder()))return true;return false;
39     }
40 }
41

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

Read the full static trace

Validate the complete shape before empty-word or size shortcuts.
Board cells are read-only UTF-16 code units. Shared row objects still represent distinct coordinate vertices. Frames below are shown bottom-to-top, not ArrayDeque iterator order.
input
{"board":["ab","ca"],"word":"aba"}
rows
2
cols
2
used
[false,false,false,false]
frames
[]
phase
"initial"
current
null
Start a candidate at a matching first letter.
used marks exactly the coordinates on this active path, not every cell visited by earlier failed paths.
input
{"board":["ab","ca"],"word":"aba"}
rows
2
cols
2
used
[true,false,false,false]
frames
[{"vertex":0,"index":0,"direction":0}]
phase
"start"
current
0
Advance the current frame’s direction cursor before testing a neighbor.
Order is up, right, down, left. An outside, already-used, or wrong-letter neighbor cannot extend this prefix. The parent cursor persists while a child is explored.
input
{"board":["ab","ca"],"word":"aba"}
rows
2
cols
2
used
[true,false,false,false]
frames
[{"vertex":0,"index":0,"direction":1}]
phase
"neighbor"
current
0
direction
0
neighbor
[-1,0]
next
null
reason
"outside"
Advance the current frame’s direction cursor before testing a neighbor.
Order is up, right, down, left. An outside, already-used, or wrong-letter neighbor cannot extend this prefix. The parent cursor persists while a child is explored.
input
{"board":["ab","ca"],"word":"aba"}
rows
2
cols
2
used
[true,false,false,false]
frames
[{"vertex":0,"index":0,"direction":2}]
phase
"neighbor"
current
0
direction
1
neighbor
[0,1]
next
1
reason
"eligible"
Claim the next matching coordinate and suspend the parent.
The new frame matches one more UTF-16 code unit. Explicit frames avoid a Java call-stack dependency for long words.
input
{"board":["ab","ca"],"word":"aba"}
rows
2
cols
2
used
[true,true,false,false]
frames
[{"vertex":0,"index":0,"direction":2},{"vertex":1,"index":1,"direction":0}]
phase
"advance"
current
1
Advance the current frame’s direction cursor before testing a neighbor.
Order is up, right, down, left. An outside, already-used, or wrong-letter neighbor cannot extend this prefix. The parent cursor persists while a child is explored.
input
{"board":["ab","ca"],"word":"aba"}
rows
2
cols
2
used
[true,true,false,false]
frames
[{"vertex":0,"index":0,"direction":2},{"vertex":1,"index":1,"direction":1}]
phase
"neighbor"
current
1
direction
0
neighbor
[-1,1]
next
null
reason
"outside"
Advance the current frame’s direction cursor before testing a neighbor.
Order is up, right, down, left. An outside, already-used, or wrong-letter neighbor cannot extend this prefix. The parent cursor persists while a child is explored.
input
{"board":["ab","ca"],"word":"aba"}
rows
2
cols
2
used
[true,true,false,false]
frames
[{"vertex":0,"index":0,"direction":2},{"vertex":1,"index":1,"direction":2}]
phase
"neighbor"
current
1
direction
1
neighbor
[0,2]
next
null
reason
"outside"
Advance the current frame’s direction cursor before testing a neighbor.
Order is up, right, down, left. An outside, already-used, or wrong-letter neighbor cannot extend this prefix. The parent cursor persists while a child is explored.
input
{"board":["ab","ca"],"word":"aba"}
rows
2
cols
2
used
[true,true,false,false]
frames
[{"vertex":0,"index":0,"direction":2},{"vertex":1,"index":1,"direction":3}]
phase
"neighbor"
current
1
direction
2
neighbor
[1,1]
next
3
reason
"eligible"
Claim the next matching coordinate and suspend the parent.
The new frame matches one more UTF-16 code unit. Explicit frames avoid a Java call-stack dependency for long words.
input
{"board":["ab","ca"],"word":"aba"}
rows
2
cols
2
used
[true,true,false,true]
frames
[{"vertex":0,"index":0,"direction":2},{"vertex":1,"index":1,"direction":3},{"vertex":3,"index":2,"direction":0}]
phase
"advance"
current
3
All word positions match on one simple orthogonal path.
This is a complete witness; the private path marks are still live until the explicit cleanup steps.
input
{"board":["ab","ca"],"word":"aba"}
rows
2
cols
2
used
[true,true,false,true]
frames
[{"vertex":0,"index":0,"direction":2},{"vertex":1,"index":1,"direction":3},{"vertex":3,"index":2,"direction":0}]
phase
"match"
current
3
Unwind one successful-path frame and release its mark.
Cleanup releases exactly the popped coordinate. Caller board values were never temporary markers.
input
{"board":["ab","ca"],"word":"aba"}
rows
2
cols
2
used
[true,true,false,false]
frames
[{"vertex":0,"index":0,"direction":2},{"vertex":1,"index":1,"direction":3}]
phase
"unwind"
current
3
Unwind one successful-path frame and release its mark.
Cleanup releases exactly the popped coordinate. Caller board values were never temporary markers.
input
{"board":["ab","ca"],"word":"aba"}
rows
2
cols
2
used
[true,false,false,false]
frames
[{"vertex":0,"index":0,"direction":2}]
phase
"unwind"
current
1
Unwind one successful-path frame and release its mark.
Cleanup releases exactly the popped coordinate. Caller board values were never temporary markers.
input
{"board":["ab","ca"],"word":"aba"}
rows
2
cols
2
used
[false,false,false,false]
frames
[]
phase
"unwind"
current
0
Return existence after the private path has been released.
used is all false and the frame stack is empty on both success and exhaustion. An empty word has the empty-path witness, even on an empty board.
input
{"board":["ab","ca"],"word":"aba"}
rows
2
cols
2
used
[false,false,false,false]
frames
[]
phase
"complete"
current
null
Return the documented result.
Exact traces preserve the original fixture. Output/history snapshots used for teaching are separate from the implementation’s live workspace.
result
true

A used coordinate cannot supply the final letter

Input: {"board":["ab","cd"],"word":"aba"} · Matching coordinate path exists: false

Step 1 of 15: Validate the complete shape before empty-word or size shortcuts.

Board cells are read-only UTF-16 code units. Shared row objects still represent distinct coordinate vertices. Frames below are shown bottom-to-top, not ArrayDeque iterator order.

Word Search — active coordinates and suspended directions

Phase: initial.

Word: "aba". Match exact UTF-16 code units; moves are up, right, down, left.

Active path — bottom → top frames, in word order

Empty.

• means claimed by the active path. Board letters never change; coordinates remain distinct when source rows alias.

Explicit Java frames — bottom → top, with next direction cursors

Empty.

State after this step
Variable	Value
input	`{"board":["ab","cd"],"word":"aba"}`
rows	`2`
cols	`2`
used	`[false,false,false,false]`
frames	`[]`
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 Frame {final int vertex,index;int direction;Frame(int vertex,int index){this.vertex=vertex;this.index=index;}}
 5     private static int columns(char[][] board,String word) {
 6         Objects.requireNonNull(board,"board");Objects.requireNonNull(word,"word");if(board.length>100000)throw new IllegalArgumentException("row limit");
 7         int cols=board.length==0?0:board[0]==null?-1:board[0].length;for(char[] row:board)if(row==null||row.length!=cols)throw new IllegalArgumentException("nonrectangular board");
 8         if((long)board.length*cols>100000)throw new IllegalArgumentException("cell limit");return cols;
 9     }
10     public static boolean exists(char[][] board,String word) {
11         int cols=columns(board,word),rows=board.length,cells=rows*cols;if(word.isEmpty())return true;if(word.length()>cells)return false;
12         boolean[] used=new boolean[cells];ArrayDeque<Frame> stack=new ArrayDeque<>();
13         for(int start=0;start<cells;start++)if(board[start/cols][start%cols]==word.charAt(0)) {
14             used[start]=true;stack.push(new Frame(start,0));
15             while(!stack.isEmpty()) {
16                 Frame current=stack.peek();
17                 if(current.index==word.length()-1) {
18                     while(!stack.isEmpty())used[stack.pop().vertex]=false;
19                     return true;
20                 }
21                 if(current.direction==4){used[current.vertex]=false;stack.pop();continue;}
22                 int[] direction=DIRECTIONS[current.direction++];int nr=current.vertex/cols+direction[0],nc=current.vertex%cols+direction[1];
23                 if(nr<0||nr>=rows||nc<0||nc>=cols)continue;int next=nr*cols+nc;
24                 if(used[next]||board[nr][nc]!=word.charAt(current.index+1))continue;
25                 used[next]=true;stack.push(new Frame(next,current.index+1));
26             }
27         }
28         return false;
29     }
30     private static boolean enumerate(char[][] board,String word,int cols,int v,boolean[] used,StringBuilder path) {
31         used[v]=true;path.append(board[v/cols][v%cols]);boolean found=false;
32         if(path.length()==word.length())found=path.toString().equals(word);
33         else for(int[] d:DIRECTIONS){int nr=v/cols+d[0],nc=v%cols+d[1];if(nr>=0&&nr<board.length&&nc>=0&&nc<cols&&!used[nr*cols+nc]&&enumerate(board,word,cols,nr*cols+nc,used,path)){found=true;break;}}
34         path.setLength(path.length()-1);used[v]=false;return found;
35     }
36     public static boolean baseline(char[][] board,String word) {
37         int cols=columns(board,word),cells=board.length*cols;if(word.isEmpty())return true;if(word.length()>cells)return false;
38         boolean[] used=new boolean[cells];for(int v=0;v<cells;v++)if(enumerate(board,word,cols,v,used,new StringBuilder()))return true;return false;
39     }
40 }
41

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

Read the full static trace

Validate the complete shape before empty-word or size shortcuts.
Board cells are read-only UTF-16 code units. Shared row objects still represent distinct coordinate vertices. Frames below are shown bottom-to-top, not ArrayDeque iterator order.
input
{"board":["ab","cd"],"word":"aba"}
rows
2
cols
2
used
[false,false,false,false]
frames
[]
phase
"initial"
current
null
Start a candidate at a matching first letter.
used marks exactly the coordinates on this active path, not every cell visited by earlier failed paths.
input
{"board":["ab","cd"],"word":"aba"}
rows
2
cols
2
used
[true,false,false,false]
frames
[{"vertex":0,"index":0,"direction":0}]
phase
"start"
current
0
Advance the current frame’s direction cursor before testing a neighbor.
Order is up, right, down, left. An outside, already-used, or wrong-letter neighbor cannot extend this prefix. The parent cursor persists while a child is explored.
input
{"board":["ab","cd"],"word":"aba"}
rows
2
cols
2
used
[true,false,false,false]
frames
[{"vertex":0,"index":0,"direction":1}]
phase
"neighbor"
current
0
direction
0
neighbor
[-1,0]
next
null
reason
"outside"
Advance the current frame’s direction cursor before testing a neighbor.
Order is up, right, down, left. An outside, already-used, or wrong-letter neighbor cannot extend this prefix. The parent cursor persists while a child is explored.
input
{"board":["ab","cd"],"word":"aba"}
rows
2
cols
2
used
[true,false,false,false]
frames
[{"vertex":0,"index":0,"direction":2}]
phase
"neighbor"
current
0
direction
1
neighbor
[0,1]
next
1
reason
"eligible"
Claim the next matching coordinate and suspend the parent.
The new frame matches one more UTF-16 code unit. Explicit frames avoid a Java call-stack dependency for long words.
input
{"board":["ab","cd"],"word":"aba"}
rows
2
cols
2
used
[true,true,false,false]
frames
[{"vertex":0,"index":0,"direction":2},{"vertex":1,"index":1,"direction":0}]
phase
"advance"
current
1
Advance the current frame’s direction cursor before testing a neighbor.
Order is up, right, down, left. An outside, already-used, or wrong-letter neighbor cannot extend this prefix. The parent cursor persists while a child is explored.
input
{"board":["ab","cd"],"word":"aba"}
rows
2
cols
2
used
[true,true,false,false]
frames
[{"vertex":0,"index":0,"direction":2},{"vertex":1,"index":1,"direction":1}]
phase
"neighbor"
current
1
direction
0
neighbor
[-1,1]
next
null
reason
"outside"
Advance the current frame’s direction cursor before testing a neighbor.
Order is up, right, down, left. An outside, already-used, or wrong-letter neighbor cannot extend this prefix. The parent cursor persists while a child is explored.
input
{"board":["ab","cd"],"word":"aba"}
rows
2
cols
2
used
[true,true,false,false]
frames
[{"vertex":0,"index":0,"direction":2},{"vertex":1,"index":1,"direction":2}]
phase
"neighbor"
current
1
direction
1
neighbor
[0,2]
next
null
reason
"outside"
Advance the current frame’s direction cursor before testing a neighbor.
Order is up, right, down, left. An outside, already-used, or wrong-letter neighbor cannot extend this prefix. The parent cursor persists while a child is explored.
input
{"board":["ab","cd"],"word":"aba"}
rows
2
cols
2
used
[true,true,false,false]
frames
[{"vertex":0,"index":0,"direction":2},{"vertex":1,"index":1,"direction":3}]
phase
"neighbor"
current
1
direction
2
neighbor
[1,1]
next
3
reason
"letter"
Advance the current frame’s direction cursor before testing a neighbor.
Order is up, right, down, left. An outside, already-used, or wrong-letter neighbor cannot extend this prefix. The parent cursor persists while a child is explored.
input
{"board":["ab","cd"],"word":"aba"}
rows
2
cols
2
used
[true,true,false,false]
frames
[{"vertex":0,"index":0,"direction":2},{"vertex":1,"index":1,"direction":4}]
phase
"neighbor"
current
1
direction
3
neighbor
[0,0]
next
0
reason
"used"
All directions failed; restore the parent continuation.
This failed prefix must release its coordinate so a sibling path or later start can use it.
input
{"board":["ab","cd"],"word":"aba"}
rows
2
cols
2
used
[true,false,false,false]
frames
[{"vertex":0,"index":0,"direction":2}]
phase
"retreat"
current
1
Advance the current frame’s direction cursor before testing a neighbor.
Order is up, right, down, left. An outside, already-used, or wrong-letter neighbor cannot extend this prefix. The parent cursor persists while a child is explored.
input
{"board":["ab","cd"],"word":"aba"}
rows
2
cols
2
used
[true,false,false,false]
frames
[{"vertex":0,"index":0,"direction":3}]
phase
"neighbor"
current
0
direction
2
neighbor
[1,0]
next
2
reason
"letter"
Advance the current frame’s direction cursor before testing a neighbor.
Order is up, right, down, left. An outside, already-used, or wrong-letter neighbor cannot extend this prefix. The parent cursor persists while a child is explored.
input
{"board":["ab","cd"],"word":"aba"}
rows
2
cols
2
used
[true,false,false,false]
frames
[{"vertex":0,"index":0,"direction":4}]
phase
"neighbor"
current
0
direction
3
neighbor
[0,-1]
next
null
reason
"outside"
All directions failed; restore the parent continuation.
This failed prefix must release its coordinate so a sibling path or later start can use it.
input
{"board":["ab","cd"],"word":"aba"}
rows
2
cols
2
used
[false,false,false,false]
frames
[]
phase
"retreat"
current
0
Return existence after the private path has been released.
used is all false and the frame stack is empty on both success and exhaustion. An empty word has the empty-path witness, even on an empty board.
input
{"board":["ab","cd"],"word":"aba"}
rows
2
cols
2
used
[false,false,false,false]
frames
[]
phase
"complete"
current
null
Return the documented result.
Exact traces preserve the original fixture. Output/history snapshots used for teaching are separate from the implementation’s live workspace.
result
false

Diagonal-only letters do not form an edge

Input: {"board":["ax","xb"],"word":"ab"} · Matching coordinate path exists: false

Step 1 of 9: Validate the complete shape before empty-word or size shortcuts.

Board cells are read-only UTF-16 code units. Shared row objects still represent distinct coordinate vertices. Frames below are shown bottom-to-top, not ArrayDeque iterator order.

Word Search — active coordinates and suspended directions

Phase: initial.

Word: "ab". Match exact UTF-16 code units; moves are up, right, down, left.

Active path — bottom → top frames, in word order

Empty.

• means claimed by the active path. Board letters never change; coordinates remain distinct when source rows alias.

Explicit Java frames — bottom → top, with next direction cursors

Empty.

State after this step
Variable	Value
input	`{"board":["ax","xb"],"word":"ab"}`
rows	`2`
cols	`2`
used	`[false,false,false,false]`
frames	`[]`
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 Frame {final int vertex,index;int direction;Frame(int vertex,int index){this.vertex=vertex;this.index=index;}}
 5     private static int columns(char[][] board,String word) {
 6         Objects.requireNonNull(board,"board");Objects.requireNonNull(word,"word");if(board.length>100000)throw new IllegalArgumentException("row limit");
 7         int cols=board.length==0?0:board[0]==null?-1:board[0].length;for(char[] row:board)if(row==null||row.length!=cols)throw new IllegalArgumentException("nonrectangular board");
 8         if((long)board.length*cols>100000)throw new IllegalArgumentException("cell limit");return cols;
 9     }
10     public static boolean exists(char[][] board,String word) {
11         int cols=columns(board,word),rows=board.length,cells=rows*cols;if(word.isEmpty())return true;if(word.length()>cells)return false;
12         boolean[] used=new boolean[cells];ArrayDeque<Frame> stack=new ArrayDeque<>();
13         for(int start=0;start<cells;start++)if(board[start/cols][start%cols]==word.charAt(0)) {
14             used[start]=true;stack.push(new Frame(start,0));
15             while(!stack.isEmpty()) {
16                 Frame current=stack.peek();
17                 if(current.index==word.length()-1) {
18                     while(!stack.isEmpty())used[stack.pop().vertex]=false;
19                     return true;
20                 }
21                 if(current.direction==4){used[current.vertex]=false;stack.pop();continue;}
22                 int[] direction=DIRECTIONS[current.direction++];int nr=current.vertex/cols+direction[0],nc=current.vertex%cols+direction[1];
23                 if(nr<0||nr>=rows||nc<0||nc>=cols)continue;int next=nr*cols+nc;
24                 if(used[next]||board[nr][nc]!=word.charAt(current.index+1))continue;
25                 used[next]=true;stack.push(new Frame(next,current.index+1));
26             }
27         }
28         return false;
29     }
30     private static boolean enumerate(char[][] board,String word,int cols,int v,boolean[] used,StringBuilder path) {
31         used[v]=true;path.append(board[v/cols][v%cols]);boolean found=false;
32         if(path.length()==word.length())found=path.toString().equals(word);
33         else for(int[] d:DIRECTIONS){int nr=v/cols+d[0],nc=v%cols+d[1];if(nr>=0&&nr<board.length&&nc>=0&&nc<cols&&!used[nr*cols+nc]&&enumerate(board,word,cols,nr*cols+nc,used,path)){found=true;break;}}
34         path.setLength(path.length()-1);used[v]=false;return found;
35     }
36     public static boolean baseline(char[][] board,String word) {
37         int cols=columns(board,word),cells=board.length*cols;if(word.isEmpty())return true;if(word.length()>cells)return false;
38         boolean[] used=new boolean[cells];for(int v=0;v<cells;v++)if(enumerate(board,word,cols,v,used,new StringBuilder()))return true;return false;
39     }
40 }
41

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

Read the full static trace

Validate the complete shape before empty-word or size shortcuts.
Board cells are read-only UTF-16 code units. Shared row objects still represent distinct coordinate vertices. Frames below are shown bottom-to-top, not ArrayDeque iterator order.
input
{"board":["ax","xb"],"word":"ab"}
rows
2
cols
2
used
[false,false,false,false]
frames
[]
phase
"initial"
current
null
Start a candidate at a matching first letter.
used marks exactly the coordinates on this active path, not every cell visited by earlier failed paths.
input
{"board":["ax","xb"],"word":"ab"}
rows
2
cols
2
used
[true,false,false,false]
frames
[{"vertex":0,"index":0,"direction":0}]
phase
"start"
current
0
Advance the current frame’s direction cursor before testing a neighbor.
Order is up, right, down, left. An outside, already-used, or wrong-letter neighbor cannot extend this prefix. The parent cursor persists while a child is explored.
input
{"board":["ax","xb"],"word":"ab"}
rows
2
cols
2
used
[true,false,false,false]
frames
[{"vertex":0,"index":0,"direction":1}]
phase
"neighbor"
current
0
direction
0
neighbor
[-1,0]
next
null
reason
"outside"
Advance the current frame’s direction cursor before testing a neighbor.
Order is up, right, down, left. An outside, already-used, or wrong-letter neighbor cannot extend this prefix. The parent cursor persists while a child is explored.
input
{"board":["ax","xb"],"word":"ab"}
rows
2
cols
2
used
[true,false,false,false]
frames
[{"vertex":0,"index":0,"direction":2}]
phase
"neighbor"
current
0
direction
1
neighbor
[0,1]
next
1
reason
"letter"
Advance the current frame’s direction cursor before testing a neighbor.
Order is up, right, down, left. An outside, already-used, or wrong-letter neighbor cannot extend this prefix. The parent cursor persists while a child is explored.
input
{"board":["ax","xb"],"word":"ab"}
rows
2
cols
2
used
[true,false,false,false]
frames
[{"vertex":0,"index":0,"direction":3}]
phase
"neighbor"
current
0
direction
2
neighbor
[1,0]
next
2
reason
"letter"
Advance the current frame’s direction cursor before testing a neighbor.
Order is up, right, down, left. An outside, already-used, or wrong-letter neighbor cannot extend this prefix. The parent cursor persists while a child is explored.
input
{"board":["ax","xb"],"word":"ab"}
rows
2
cols
2
used
[true,false,false,false]
frames
[{"vertex":0,"index":0,"direction":4}]
phase
"neighbor"
current
0
direction
3
neighbor
[0,-1]
next
null
reason
"outside"
All directions failed; restore the parent continuation.
This failed prefix must release its coordinate so a sibling path or later start can use it.
input
{"board":["ax","xb"],"word":"ab"}
rows
2
cols
2
used
[false,false,false,false]
frames
[]
phase
"retreat"
current
0
Return existence after the private path has been released.
used is all false and the frame stack is empty on both success and exhaustion. An empty word has the empty-path witness, even on an empty board.
input
{"board":["ax","xb"],"word":"ab"}
rows
2
cols
2
used
[false,false,false,false]
frames
[]
phase
"complete"
current
null
Return the documented result.
Exact traces preserve the original fixture. Output/history snapshots used for teaching are separate from the implementation’s live workspace.
result
false

The empty word on zero-column rows

Input: {"board":["",""],"word":""} · Matching coordinate path exists: true

Step 1 of 3: Validate the complete shape before empty-word or size shortcuts.

Board cells are read-only UTF-16 code units. Shared row objects still represent distinct coordinate vertices. Frames below are shown bottom-to-top, not ArrayDeque iterator order.

Word Search — active coordinates and suspended directions

Phase: initial.

Word: "". Match exact UTF-16 code units; moves are up, right, down, left.

No cell vertices.

Active path — bottom → top frames, in word order

Empty.

• means claimed by the active path. Board letters never change; coordinates remain distinct when source rows alias.

The empty path matches the empty word, even without a start coordinate.

Explicit Java frames — bottom → top, with next direction cursors

Empty.

State after this step
Variable	Value
input	`{"board":["",""],"word":""}`
rows	`2`
cols	`0`
used	`[]`
frames	`[]`
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 Frame {final int vertex,index;int direction;Frame(int vertex,int index){this.vertex=vertex;this.index=index;}}
 5     private static int columns(char[][] board,String word) {
 6         Objects.requireNonNull(board,"board");Objects.requireNonNull(word,"word");if(board.length>100000)throw new IllegalArgumentException("row limit");
 7         int cols=board.length==0?0:board[0]==null?-1:board[0].length;for(char[] row:board)if(row==null||row.length!=cols)throw new IllegalArgumentException("nonrectangular board");
 8         if((long)board.length*cols>100000)throw new IllegalArgumentException("cell limit");return cols;
 9     }
10     public static boolean exists(char[][] board,String word) {
11         int cols=columns(board,word),rows=board.length,cells=rows*cols;if(word.isEmpty())return true;if(word.length()>cells)return false;
12         boolean[] used=new boolean[cells];ArrayDeque<Frame> stack=new ArrayDeque<>();
13         for(int start=0;start<cells;start++)if(board[start/cols][start%cols]==word.charAt(0)) {
14             used[start]=true;stack.push(new Frame(start,0));
15             while(!stack.isEmpty()) {
16                 Frame current=stack.peek();
17                 if(current.index==word.length()-1) {
18                     while(!stack.isEmpty())used[stack.pop().vertex]=false;
19                     return true;
20                 }
21                 if(current.direction==4){used[current.vertex]=false;stack.pop();continue;}
22                 int[] direction=DIRECTIONS[current.direction++];int nr=current.vertex/cols+direction[0],nc=current.vertex%cols+direction[1];
23                 if(nr<0||nr>=rows||nc<0||nc>=cols)continue;int next=nr*cols+nc;
24                 if(used[next]||board[nr][nc]!=word.charAt(current.index+1))continue;
25                 used[next]=true;stack.push(new Frame(next,current.index+1));
26             }
27         }
28         return false;
29     }
30     private static boolean enumerate(char[][] board,String word,int cols,int v,boolean[] used,StringBuilder path) {
31         used[v]=true;path.append(board[v/cols][v%cols]);boolean found=false;
32         if(path.length()==word.length())found=path.toString().equals(word);
33         else for(int[] d:DIRECTIONS){int nr=v/cols+d[0],nc=v%cols+d[1];if(nr>=0&&nr<board.length&&nc>=0&&nc<cols&&!used[nr*cols+nc]&&enumerate(board,word,cols,nr*cols+nc,used,path)){found=true;break;}}
34         path.setLength(path.length()-1);used[v]=false;return found;
35     }
36     public static boolean baseline(char[][] board,String word) {
37         int cols=columns(board,word),cells=board.length*cols;if(word.isEmpty())return true;if(word.length()>cells)return false;
38         boolean[] used=new boolean[cells];for(int v=0;v<cells;v++)if(enumerate(board,word,cols,v,used,new StringBuilder()))return true;return false;
39     }
40 }
41

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

Read the full static trace

Validate the complete shape before empty-word or size shortcuts.
Board cells are read-only UTF-16 code units. Shared row objects still represent distinct coordinate vertices. Frames below are shown bottom-to-top, not ArrayDeque iterator order.
input
{"board":["",""],"word":""}
rows
2
cols
0
used
[]
frames
[]
phase
"initial"
current
null
Return existence after the private path has been released.
used is all false and the frame stack is empty on both success and exhaustion. An empty word has the empty-path witness, even on an empty board.
input
{"board":["",""],"word":""}
rows
2
cols
0
used
[]
frames
[]
phase
"complete"
current
null
Return the documented result.
Exact traces preserve the original fixture. Output/history snapshots used for teaching are separate from the implementation’s live workspace.
result
true

A nonempty word with no cells

Input: {"board":[],"word":"a"} · Matching coordinate path exists: false

Step 1 of 4: Validate the complete shape before empty-word or size shortcuts.

Board cells are read-only UTF-16 code units. Shared row objects still represent distinct coordinate vertices. Frames below are shown bottom-to-top, not ArrayDeque iterator order.

Word Search — active coordinates and suspended directions

Phase: initial.

Word: "a". Match exact UTF-16 code units; moves are up, right, down, left.

No cell vertices.

Active path — bottom → top frames, in word order

Empty.

• means claimed by the active path. Board letters never change; coordinates remain distinct when source rows alias.

Explicit Java frames — bottom → top, with next direction cursors

Empty.

State after this step
Variable	Value
input	`{"board":[],"word":"a"}`
rows	`0`
cols	`0`
used	`[]`
frames	`[]`
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 Frame {final int vertex,index;int direction;Frame(int vertex,int index){this.vertex=vertex;this.index=index;}}
 5     private static int columns(char[][] board,String word) {
 6         Objects.requireNonNull(board,"board");Objects.requireNonNull(word,"word");if(board.length>100000)throw new IllegalArgumentException("row limit");
 7         int cols=board.length==0?0:board[0]==null?-1:board[0].length;for(char[] row:board)if(row==null||row.length!=cols)throw new IllegalArgumentException("nonrectangular board");
 8         if((long)board.length*cols>100000)throw new IllegalArgumentException("cell limit");return cols;
 9     }
10     public static boolean exists(char[][] board,String word) {
11         int cols=columns(board,word),rows=board.length,cells=rows*cols;if(word.isEmpty())return true;if(word.length()>cells)return false;
12         boolean[] used=new boolean[cells];ArrayDeque<Frame> stack=new ArrayDeque<>();
13         for(int start=0;start<cells;start++)if(board[start/cols][start%cols]==word.charAt(0)) {
14             used[start]=true;stack.push(new Frame(start,0));
15             while(!stack.isEmpty()) {
16                 Frame current=stack.peek();
17                 if(current.index==word.length()-1) {
18                     while(!stack.isEmpty())used[stack.pop().vertex]=false;
19                     return true;
20                 }
21                 if(current.direction==4){used[current.vertex]=false;stack.pop();continue;}
22                 int[] direction=DIRECTIONS[current.direction++];int nr=current.vertex/cols+direction[0],nc=current.vertex%cols+direction[1];
23                 if(nr<0||nr>=rows||nc<0||nc>=cols)continue;int next=nr*cols+nc;
24                 if(used[next]||board[nr][nc]!=word.charAt(current.index+1))continue;
25                 used[next]=true;stack.push(new Frame(next,current.index+1));
26             }
27         }
28         return false;
29     }
30     private static boolean enumerate(char[][] board,String word,int cols,int v,boolean[] used,StringBuilder path) {
31         used[v]=true;path.append(board[v/cols][v%cols]);boolean found=false;
32         if(path.length()==word.length())found=path.toString().equals(word);
33         else for(int[] d:DIRECTIONS){int nr=v/cols+d[0],nc=v%cols+d[1];if(nr>=0&&nr<board.length&&nc>=0&&nc<cols&&!used[nr*cols+nc]&&enumerate(board,word,cols,nr*cols+nc,used,path)){found=true;break;}}
34         path.setLength(path.length()-1);used[v]=false;return found;
35     }
36     public static boolean baseline(char[][] board,String word) {
37         int cols=columns(board,word),cells=board.length*cols;if(word.isEmpty())return true;if(word.length()>cells)return false;
38         boolean[] used=new boolean[cells];for(int v=0;v<cells;v++)if(enumerate(board,word,cols,v,used,new StringBuilder()))return true;return false;
39     }
40 }
41

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

Read the full static trace

Validate the complete shape before empty-word or size shortcuts.
Board cells are read-only UTF-16 code units. Shared row objects still represent distinct coordinate vertices. Frames below are shown bottom-to-top, not ArrayDeque iterator order.
input
{"board":[],"word":"a"}
rows
0
cols
0
used
[]
frames
[]
phase
"initial"
current
null
A simple coordinate path cannot use more cells than exist.
Length is a necessary bound, not a reachability proof; no coordinate may repeat within a candidate word.
input
{"board":[],"word":"a"}
rows
0
cols
0
used
[]
frames
[]
phase
"too-long"
current
null
Return existence after the private path has been released.
used is all false and the frame stack is empty on both success and exhaustion. An empty word has the empty-path witness, even on an empty board.
input
{"board":[],"word":"a"}
rows
0
cols
0
used
[]
frames
[]
phase
"complete"
current
null
Return the documented result.
Exact traces preserve the original fixture. Output/history snapshots used for teaching are separate from the implementation’s live workspace.
result
false

Exact non-ASCII code units

Input: {"board":["λa"],"word":"λa"} · Matching coordinate path exists: true

Step 1 of 10: Validate the complete shape before empty-word or size shortcuts.

Board cells are read-only UTF-16 code units. Shared row objects still represent distinct coordinate vertices. Frames below are shown bottom-to-top, not ArrayDeque iterator order.

Word Search — active coordinates and suspended directions

Phase: initial.

Word: "λa". Match exact UTF-16 code units; moves are up, right, down, left.

λa

Active path — bottom → top frames, in word order

Empty.

• means claimed by the active path. Board letters never change; coordinates remain distinct when source rows alias.

Explicit Java frames — bottom → top, with next direction cursors

Empty.

State after this step
Variable	Value
input	`{"board":["λa"],"word":"λa"}`
rows	`1`
cols	`2`
used	`[false,false]`
frames	`[]`
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 Frame {final int vertex,index;int direction;Frame(int vertex,int index){this.vertex=vertex;this.index=index;}}
 5     private static int columns(char[][] board,String word) {
 6         Objects.requireNonNull(board,"board");Objects.requireNonNull(word,"word");if(board.length>100000)throw new IllegalArgumentException("row limit");
 7         int cols=board.length==0?0:board[0]==null?-1:board[0].length;for(char[] row:board)if(row==null||row.length!=cols)throw new IllegalArgumentException("nonrectangular board");
 8         if((long)board.length*cols>100000)throw new IllegalArgumentException("cell limit");return cols;
 9     }
10     public static boolean exists(char[][] board,String word) {
11         int cols=columns(board,word),rows=board.length,cells=rows*cols;if(word.isEmpty())return true;if(word.length()>cells)return false;
12         boolean[] used=new boolean[cells];ArrayDeque<Frame> stack=new ArrayDeque<>();
13         for(int start=0;start<cells;start++)if(board[start/cols][start%cols]==word.charAt(0)) {
14             used[start]=true;stack.push(new Frame(start,0));
15             while(!stack.isEmpty()) {
16                 Frame current=stack.peek();
17                 if(current.index==word.length()-1) {
18                     while(!stack.isEmpty())used[stack.pop().vertex]=false;
19                     return true;
20                 }
21                 if(current.direction==4){used[current.vertex]=false;stack.pop();continue;}
22                 int[] direction=DIRECTIONS[current.direction++];int nr=current.vertex/cols+direction[0],nc=current.vertex%cols+direction[1];
23                 if(nr<0||nr>=rows||nc<0||nc>=cols)continue;int next=nr*cols+nc;
24                 if(used[next]||board[nr][nc]!=word.charAt(current.index+1))continue;
25                 used[next]=true;stack.push(new Frame(next,current.index+1));
26             }
27         }
28         return false;
29     }
30     private static boolean enumerate(char[][] board,String word,int cols,int v,boolean[] used,StringBuilder path) {
31         used[v]=true;path.append(board[v/cols][v%cols]);boolean found=false;
32         if(path.length()==word.length())found=path.toString().equals(word);
33         else for(int[] d:DIRECTIONS){int nr=v/cols+d[0],nc=v%cols+d[1];if(nr>=0&&nr<board.length&&nc>=0&&nc<cols&&!used[nr*cols+nc]&&enumerate(board,word,cols,nr*cols+nc,used,path)){found=true;break;}}
34         path.setLength(path.length()-1);used[v]=false;return found;
35     }
36     public static boolean baseline(char[][] board,String word) {
37         int cols=columns(board,word),cells=board.length*cols;if(word.isEmpty())return true;if(word.length()>cells)return false;
38         boolean[] used=new boolean[cells];for(int v=0;v<cells;v++)if(enumerate(board,word,cols,v,used,new StringBuilder()))return true;return false;
39     }
40 }
41

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

Read the full static trace

Validate the complete shape before empty-word or size shortcuts.
Board cells are read-only UTF-16 code units. Shared row objects still represent distinct coordinate vertices. Frames below are shown bottom-to-top, not ArrayDeque iterator order.
input
{"board":["λa"],"word":"λa"}
rows
1
cols
2
used
[false,false]
frames
[]
phase
"initial"
current
null
Start a candidate at a matching first letter.
used marks exactly the coordinates on this active path, not every cell visited by earlier failed paths.
input
{"board":["λa"],"word":"λa"}
rows
1
cols
2
used
[true,false]
frames
[{"vertex":0,"index":0,"direction":0}]
phase
"start"
current
0
Advance the current frame’s direction cursor before testing a neighbor.
Order is up, right, down, left. An outside, already-used, or wrong-letter neighbor cannot extend this prefix. The parent cursor persists while a child is explored.
input
{"board":["λa"],"word":"λa"}
rows
1
cols
2
used
[true,false]
frames
[{"vertex":0,"index":0,"direction":1}]
phase
"neighbor"
current
0
direction
0
neighbor
[-1,0]
next
null
reason
"outside"
Advance the current frame’s direction cursor before testing a neighbor.
Order is up, right, down, left. An outside, already-used, or wrong-letter neighbor cannot extend this prefix. The parent cursor persists while a child is explored.
input
{"board":["λa"],"word":"λa"}
rows
1
cols
2
used
[true,false]
frames
[{"vertex":0,"index":0,"direction":2}]
phase
"neighbor"
current
0
direction
1
neighbor
[0,1]
next
1
reason
"eligible"
Claim the next matching coordinate and suspend the parent.
The new frame matches one more UTF-16 code unit. Explicit frames avoid a Java call-stack dependency for long words.
input
{"board":["λa"],"word":"λa"}
rows
1
cols
2
used
[true,true]
frames
[{"vertex":0,"index":0,"direction":2},{"vertex":1,"index":1,"direction":0}]
phase
"advance"
current
1
All word positions match on one simple orthogonal path.
This is a complete witness; the private path marks are still live until the explicit cleanup steps.
input
{"board":["λa"],"word":"λa"}
rows
1
cols
2
used
[true,true]
frames
[{"vertex":0,"index":0,"direction":2},{"vertex":1,"index":1,"direction":0}]
phase
"match"
current
1
Unwind one successful-path frame and release its mark.
Cleanup releases exactly the popped coordinate. Caller board values were never temporary markers.
input
{"board":["λa"],"word":"λa"}
rows
1
cols
2
used
[true,false]
frames
[{"vertex":0,"index":0,"direction":2}]
phase
"unwind"
current
1
Unwind one successful-path frame and release its mark.
Cleanup releases exactly the popped coordinate. Caller board values were never temporary markers.
input
{"board":["λa"],"word":"λa"}
rows
1
cols
2
used
[false,false]
frames
[]
phase
"unwind"
current
0
Return existence after the private path has been released.
used is all false and the frame stack is empty on both success and exhaustion. An empty word has the empty-path witness, even on an empty board.
input
{"board":["λa"],"word":"λa"}
rows
1
cols
2
used
[false,false]
frames
[]
phase
"complete"
current
null
Return the documented result.
Exact traces preserve the original fixture. Output/history snapshots used for teaching are separate from the implementation’s live workspace.
result
true

Test the contract

Input: Empty word on empty and zero-column boards
Output: true
Full shape validation still precedes success.
Input: A word that requires coordinate reuse or a diagonal
Output: false
Separates legal paths from letter presence alone.
Input: Every binary board through 2×3 and binary words through length five
Output: matches layered coordinate-mask reachability
The independent oracle is breadth by word position, not DFS frames.
Input: Shared rows and non-ASCII BMP letters
Output: correct result with unchanged values and row identities
Coordinate ownership and exact char matching are tested.
Input: 100,000-cell matching corridor
Output: true without recursive stack overflow
The explicit main stack supports the declared depth boundary.

Common mistakes and counterexamples

Use global visited across branches

Counterexample: A cell rejected under one prefix may be needed by a later valid start.

Mark only the active path and release on every backtrack.

Allow coordinate reuse or diagonal moves

Counterexample: The only route for a claimed word may return to its first a or jump diagonally.

Check used and exactly four orthogonal directions.

Return true while source cells still contain temporary markers

Counterexample: Successful early return can leave the caller’s board corrupted.

Keep source read-only and explicitly release the private frame path.

Assume a char always means a Unicode grapheme

Counterexample: Supplementary characters use surrogate pairs in Java Strings.

State the UTF-16 code-unit contract or redesign storage for code points/graphemes.

Follow-ups

Return one matching path.

Copy frame coordinates at the match step before cleanup, then return a fresh ordered witness. Specify an impossible outcome and whether the first row-major/direction-order witness is required. Account for O(L) output storage.

Search many words at once.

Use a trie to share prefix exploration and define duplicate-word output semantics, as in DSA-091. Keep coordinate marks path-local and terminal consumption local to the call rather than mutating a shared dictionary unexpectedly.

Add frequency and start-end pruning.

A character-frequency feasibility check can reject impossible supply. Reversing the word when its last letter is rarer preserves existence on this undirected graph, but changes which witness appears first. Derive these optimizations without replacing the no-reuse constraint.

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 · 176/20,000 characters

Self-review

Can I reconstruct the suspended direction cursor after a child returns?Can I prove used equals the active frame path, rather than global discovery?Can I explain empty paths, shared rows, successful cleanup, and UTF-16 matching?

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

Related foundations

Keep practicing

Open focused practice

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