Workspace Code & DSA
Learning pathsPricingA
← DSA problem library

DSA-090 · Branch a pattern over existing trie edges while retaining consumed depth

Word Dictionary with Wildcard Search

Core · Java 21 · Version 1 · editorial draft

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

Understand the problem

Maintain a dictionary with add(word) and search(pattern). Lowercase letters match themselves; each dot matches exactly one lowercase letter. Return whether a complete stored word matches the complete pattern.

  • Each instance owns a mutable lowercase-ASCII trie. Empty words are allowed; duplicate additions are idempotent. A dot is permitted only in a search pattern and matches one character, never zero or many. This is not a general regular-expression API.
  • Words and patterns are nonnull with length at most 10,000; cumulative added character count per instance is at most 100,000. Size bounds are preconditions. Null throws NullPointerException; any other unsupported character throws IllegalArgumentException. Validate the entire string before an add can allocate or mark nodes.
  • add is void; search is read-only and does not allocate trie nodes or change terminal flags. Query State frames are permitted auxiliary allocations. Instances are independent and not thread-safe; no deletion is provided. Empty search succeeds exactly when the root has been marked terminal by add("").

Examples

  1. Input: add bad,dad,mad; search .ad
    Output: true

    A dot explores existing first-letter alternatives; the remaining literal suffix must match.

  2. Input: add bad; search ba
    Output: false

    The ba path exists but is not a complete stored word.

  3. Input: add empty word; search empty pattern
    Output: true

    Zero characters consume zero edges, so only root terminal state decides.

Before you start

  • Trie paths versus terminal words (DSA-089)
  • Explicit DFS frontiers and exact-length wildcard semantics

Recognize the structure

A search state needs both a trie node and a consumed pattern index. Prefix sharing reduces duplicate dictionary work, but a wildcard creates multiple candidate states; one greedy branch cannot decide the answer.

Try before revealing

Hint 1

A trie path is not necessarily a stored complete word.

Hint 2

A dot branches over children and consumes exactly one position.

Hint 3

Store (node,index) states; accept only an exhausted terminal state.

Derive the solution

Reveal the baseline, optimized reasoning, and Java code

Scan the stored word set

Keep a HashSet of complete words. For each search, skip words with the wrong length and compare every position, accepting a dot or an equal literal. For pattern .ad and stored bad,dad,mad, any one full positional match proves true. This compiles as the Baseline class and makes exact length and duplicate semantics explicit; query work can repeat a common prefix across many words.

Improve the baseline

Validate before mutation

Check every character of an added word before traversing or allocating its path. Otherwise a late invalid character could leave a partially inserted prefix.

Use nullable-free search entries

Push State(root,0). A literal follows at most one existing child; a dot pushes every existing child with index+1. Reverse child pushing gives an illustrative a-first DFS without changing boolean semantics.

Require terminal state at exact exhaustion

At index==pattern.length(), accept only a terminal node. A nonterminal exhausted candidate fails locally but other pending alternatives may still match. Exhausting all work returns false.

Why it is correct

State invariant

A state (node,i) represents exactly the stored prefix of length i that matches the first i pattern positions. Root at i=0 initializes this meaning.

Preserve complete alternatives

A literal permits only its identical edge. A dot permits every existing one-letter edge, each consuming exactly one position. Expanding all such children loses no potential matching word and invents no invalid prefix.

Correct decision and no mutation

An exhausted terminal state is a full stored word of the required length; an exhausted nonterminal is only a prefix. If the frontier empties, no full witness exists. Search reads children/terminal flags only, so it preserves the dictionary.

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 void validate(String text, boolean pattern) {
        Objects.requireNonNull(text,"text");
        for (int i = 0; i < text.length(); i++) {
            char c = text.charAt(i);
            if ((c < 'a' || c > 'z') && !(pattern && c == '.')) throw new IllegalArgumentException("expected lowercase ASCII" );
        }
    }
    public static final class WordDictionary {
        private static final class Node {
            final Node[] children = new Node[26];
            boolean terminal;
        }
        private record State(Node node, int index) {}
        private final Node root = new Node();
        public void add(String word) {
            validate(word,false);
            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.terminal = true;
        }
        public boolean search(String pattern) {
            validate(pattern,true);
            ArrayDeque<State> stack = new ArrayDeque<>();
            stack.push(new State(root,0));
            while (!stack.isEmpty()) {
                State state = stack.pop();
                if (state.index == pattern.length()) {
                    if (state.node.terminal) return true;
                    continue;
                }
                char c = pattern.charAt(state.index);
                if (c == '.') {
                    for (int slot = 25; slot >= 0; slot--) if (state.node.children[slot] != null) stack.push(new State(state.node.children[slot],state.index+1));
                } else {
                    Node child = state.node.children[c-'a'];
                    if (child != null) stack.push(new State(child,state.index+1));
                }
            }
            return false;
        }
    }
    public static final class Baseline {
        private final Set<String> words = new HashSet<>();
        public void add(String word) { validate(word,false); words.add(word); }
        public boolean search(String pattern) {
            validate(pattern,true);
            for (String word : words) {
                if (word.length() != pattern.length()) continue;
                boolean matches = true;
                for (int i = 0; i < word.length(); i++) if (pattern.charAt(i) != '.' && pattern.charAt(i) != word.charAt(i)) { matches = false; break; }
                if (matches) return true;
            }
            return false;
        }
    }
}

Read the meaningful blocks

Terminal root is deliberate

Empty add changes only root. Merely creating an empty dictionary does not store the empty word.

Stack entries are not trie nodes

search may allocate State objects; the no-allocation promise concerns the retained trie graph, not all temporary Java objects.

Separate traversal order from API result

The reference pushes z-to-a so a is popped first. Remaining alternatives can be abandoned on true; the API promises a boolean, not a matching word or HashSet order.

Complexity

Let T be retained trie nodes, L pattern length and V the candidate nodes visited in a query. Add is O(word length+1), with at most that many new nodes. Search costs O(L+26V), including full validation and child scans; V<=T because each trie node has one fixed depth/path. Wildcards can visit a large fraction of the dictionary, so search is not unconditionally O(L).

DFS retains at most O(min(T,26L+1)) candidate frames: each level can leave at most 25 siblings pending. The trie uses O(T) retained space for fixed alphabet size 26. Baseline search takes O(L+D(L+1)) worst-case work for D distinct words, including length checks; its retained strings/set occupy O(S+D) for S stored characters.

Exact-state walkthroughs

Reveal normal and boundary traces

Whole words, prefix-only paths, and wildcard branching

Input: {"operations":[["add","bad"],["add","dad"],["add","mad"],["search","pad"],["search",".ad"],["search","ba"],["add","ba"],["search","ba"]]} · Operation outcomes: [null,null,null,false,true,false,null,true]

Step 1 of 36: Create an instance-owned empty trie.

The root path exists but is not terminal. Sorted path cards are a logical trie view, not child-array iteration or extra stored word strings.

Wildcard dictionary — consumed pattern depth and terminal words

Phase: initial.

Trie paths — sorted logical display

  • (root / empty path)prefix path only

Operation index: -1. Pattern: no active query.

Query candidates — stack top at right

Empty.

Completed operation outcomes — null means void add

Empty.

A dot consumes one edge. Complete pattern consumption still needs a terminal node. Pending alternatives at a successful query return are abandoned; they are not trie nodes and do not survive into the next call.

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
VariableValue
paths[""]
terminals[]
outcomes[]
stack[]
operationIndex-1
phase"initial"
prefix""
patternnull
See the affected Java block
 1 import java.util.*;
 2 public final class Solution {
 3     private static void validate(String text, boolean pattern) {
 4         Objects.requireNonNull(text,"text");
 5         for (int i = 0; i < text.length(); i++) {
 6             char c = text.charAt(i);
 7             if ((c < 'a' || c > 'z') && !(pattern && c == '.')) throw new IllegalArgumentException("expected lowercase ASCII" );
 8         }
 9     }
10     public static final class WordDictionary {
11         private static final class Node {
12             final Node[] children = new Node[26];
13             boolean terminal;
14         }
15         private record State(Node node, int index) {}
16         private final Node root = new Node();
17         public void add(String word) {
18             validate(word,false);
19             Node node = root;
20             for (int i = 0; i < word.length(); i++) {
21                 int slot = word.charAt(i)-'a';
22                 if (node.children[slot] == null) node.children[slot] = new Node();
23                 node = node.children[slot];
24             }
25             node.terminal = true;
26         }
27         public boolean search(String pattern) {
28             validate(pattern,true);
29             ArrayDeque<State> stack = new ArrayDeque<>();
30             stack.push(new State(root,0));
31             while (!stack.isEmpty()) {
32                 State state = stack.pop();
33                 if (state.index == pattern.length()) {
34                     if (state.node.terminal) return true;
35                     continue;
36                 }
37                 char c = pattern.charAt(state.index);
38                 if (c == '.') {
39                     for (int slot = 25; slot >= 0; slot--) if (state.node.children[slot] != null) stack.push(new State(state.node.children[slot],state.index+1));
40                 } else {
41                     Node child = state.node.children[c-'a'];
42                     if (child != null) stack.push(new State(child,state.index+1));
43                 }
44             }
45             return false;
46         }
47     }
48     public static final class Baseline {
49         private final Set<String> words = new HashSet<>();
50         public void add(String word) { validate(word,false); words.add(word); }
51         public boolean search(String pattern) {
52             validate(pattern,true);
53             for (String word : words) {
54                 if (word.length() != pattern.length()) continue;
55                 boolean matches = true;
56                 for (int i = 0; i < word.length(); i++) if (pattern.charAt(i) != '.' && pattern.charAt(i) != word.charAt(i)) { matches = false; break; }
57                 if (matches) return true;
58             }
59             return false;
60         }
61     }
62 }
63

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

Read the full static trace
  1. Create an instance-owned empty trie.

    The root path exists but is not terminal. Sorted path cards are a logical trie view, not child-array iteration or extra stored word strings.

    paths
    [""]
    terminals
    []
    outcomes
    []
    stack
    []
    operationIndex
    -1
    phase
    "initial"
    prefix
    ""
    pattern
    null
  2. Follow or allocate one validated lowercase edge.

    All characters were validated before any trie mutation. Duplicate insertion reuses existing nodes.

    paths
    ["","b"]
    terminals
    []
    outcomes
    []
    stack
    []
    operationIndex
    0
    phase
    "add-edge"
    operation
    "add"
    prefix
    "b"
    allocated
    true
    word
    "bad"
    pattern
    null
  3. Follow or allocate one validated lowercase edge.

    All characters were validated before any trie mutation. Duplicate insertion reuses existing nodes.

    paths
    ["","b","ba"]
    terminals
    []
    outcomes
    []
    stack
    []
    operationIndex
    0
    phase
    "add-edge"
    operation
    "add"
    prefix
    "ba"
    allocated
    true
    word
    "bad"
    pattern
    null
  4. Follow or allocate one validated lowercase edge.

    All characters were validated before any trie mutation. Duplicate insertion reuses existing nodes.

    paths
    ["","b","ba","bad"]
    terminals
    []
    outcomes
    []
    stack
    []
    operationIndex
    0
    phase
    "add-edge"
    operation
    "add"
    prefix
    "bad"
    allocated
    true
    word
    "bad"
    pattern
    null
  5. Mark only the complete word terminal.

    null labels the void add outcome. Empty insertion marks the root; an existing longer path does not automatically mark its prefixes.

    paths
    ["","b","ba","bad"]
    terminals
    ["bad"]
    outcomes
    [null]
    stack
    []
    operationIndex
    0
    phase
    "add-terminal"
    operation
    "add"
    prefix
    "bad"
    word
    "bad"
    pattern
    null
  6. Follow or allocate one validated lowercase edge.

    All characters were validated before any trie mutation. Duplicate insertion reuses existing nodes.

    paths
    ["","b","ba","bad","d"]
    terminals
    ["bad"]
    outcomes
    [null]
    stack
    []
    operationIndex
    1
    phase
    "add-edge"
    operation
    "add"
    prefix
    "d"
    allocated
    true
    word
    "dad"
    pattern
    null
  7. Follow or allocate one validated lowercase edge.

    All characters were validated before any trie mutation. Duplicate insertion reuses existing nodes.

    paths
    ["","b","ba","bad","d","da"]
    terminals
    ["bad"]
    outcomes
    [null]
    stack
    []
    operationIndex
    1
    phase
    "add-edge"
    operation
    "add"
    prefix
    "da"
    allocated
    true
    word
    "dad"
    pattern
    null
  8. Follow or allocate one validated lowercase edge.

    All characters were validated before any trie mutation. Duplicate insertion reuses existing nodes.

    paths
    ["","b","ba","bad","d","da","dad"]
    terminals
    ["bad"]
    outcomes
    [null]
    stack
    []
    operationIndex
    1
    phase
    "add-edge"
    operation
    "add"
    prefix
    "dad"
    allocated
    true
    word
    "dad"
    pattern
    null
  9. Mark only the complete word terminal.

    null labels the void add outcome. Empty insertion marks the root; an existing longer path does not automatically mark its prefixes.

    paths
    ["","b","ba","bad","d","da","dad"]
    terminals
    ["bad","dad"]
    outcomes
    [null,null]
    stack
    []
    operationIndex
    1
    phase
    "add-terminal"
    operation
    "add"
    prefix
    "dad"
    word
    "dad"
    pattern
    null
  10. Follow or allocate one validated lowercase edge.

    All characters were validated before any trie mutation. Duplicate insertion reuses existing nodes.

    paths
    ["","b","ba","bad","d","da","dad","m"]
    terminals
    ["bad","dad"]
    outcomes
    [null,null]
    stack
    []
    operationIndex
    2
    phase
    "add-edge"
    operation
    "add"
    prefix
    "m"
    allocated
    true
    word
    "mad"
    pattern
    null
  11. Follow or allocate one validated lowercase edge.

    All characters were validated before any trie mutation. Duplicate insertion reuses existing nodes.

    paths
    ["","b","ba","bad","d","da","dad","m","ma"]
    terminals
    ["bad","dad"]
    outcomes
    [null,null]
    stack
    []
    operationIndex
    2
    phase
    "add-edge"
    operation
    "add"
    prefix
    "ma"
    allocated
    true
    word
    "mad"
    pattern
    null
  12. Follow or allocate one validated lowercase edge.

    All characters were validated before any trie mutation. Duplicate insertion reuses existing nodes.

    paths
    ["","b","ba","bad","d","da","dad","m","ma","mad"]
    terminals
    ["bad","dad"]
    outcomes
    [null,null]
    stack
    []
    operationIndex
    2
    phase
    "add-edge"
    operation
    "add"
    prefix
    "mad"
    allocated
    true
    word
    "mad"
    pattern
    null
  13. Mark only the complete word terminal.

    null labels the void add outcome. Empty insertion marks the root; an existing longer path does not automatically mark its prefixes.

    paths
    ["","b","ba","bad","d","da","dad","m","ma","mad"]
    terminals
    ["bad","dad","mad"]
    outcomes
    [null,null,null]
    stack
    []
    operationIndex
    2
    phase
    "add-terminal"
    operation
    "add"
    prefix
    "mad"
    word
    "mad"
    pattern
    null
  14. Begin a read-only exact-length pattern search.

    Stack top is at the right. A dot consumes exactly one letter; query frames may allocate, but trie nodes and terminal flags never change.

    paths
    ["","b","ba","bad","d","da","dad","m","ma","mad"]
    terminals
    ["bad","dad","mad"]
    outcomes
    [null,null,null]
    stack
    [{"prefix":"","index":0}]
    operationIndex
    3
    phase
    "search-start"
    operation
    "search"
    pattern
    "pad"
    prefix
    null
  15. Process one candidate prefix at its consumed pattern depth.

    A complete consumed pattern succeeds only at a terminal node. Reverse child pushing yields illustrative a-first DFS; pending alternatives are abandoned on early success.

    paths
    ["","b","ba","bad","d","da","dad","m","ma","mad"]
    terminals
    ["bad","dad","mad"]
    outcomes
    [null,null,null]
    stack
    []
    operationIndex
    3
    phase
    "missing"
    operation
    "search"
    pattern
    "pad"
    prefix
    ""
    current
    {"prefix":"","index":0}
  16. Complete the boolean query without changing the dictionary.

    Outstanding alternative frames, if any, belong to this finished query and are discarded before the next call.

    paths
    ["","b","ba","bad","d","da","dad","m","ma","mad"]
    terminals
    ["bad","dad","mad"]
    outcomes
    [null,null,null,false]
    stack
    []
    operationIndex
    3
    phase
    "search-result"
    operation
    "search"
    pattern
    "pad"
    prefix
    null
    answer
    false
  17. Begin a read-only exact-length pattern search.

    Stack top is at the right. A dot consumes exactly one letter; query frames may allocate, but trie nodes and terminal flags never change.

    paths
    ["","b","ba","bad","d","da","dad","m","ma","mad"]
    terminals
    ["bad","dad","mad"]
    outcomes
    [null,null,null,false]
    stack
    [{"prefix":"","index":0}]
    operationIndex
    4
    phase
    "search-start"
    operation
    "search"
    pattern
    ".ad"
    prefix
    null
  18. Process one candidate prefix at its consumed pattern depth.

    A complete consumed pattern succeeds only at a terminal node. Reverse child pushing yields illustrative a-first DFS; pending alternatives are abandoned on early success.

    paths
    ["","b","ba","bad","d","da","dad","m","ma","mad"]
    terminals
    ["bad","dad","mad"]
    outcomes
    [null,null,null,false]
    stack
    [{"prefix":"m","index":1},{"prefix":"d","index":1},{"prefix":"b","index":1}]
    operationIndex
    4
    phase
    "branch"
    operation
    "search"
    pattern
    ".ad"
    prefix
    ""
    current
    {"prefix":"","index":0}
  19. Process one candidate prefix at its consumed pattern depth.

    A complete consumed pattern succeeds only at a terminal node. Reverse child pushing yields illustrative a-first DFS; pending alternatives are abandoned on early success.

    paths
    ["","b","ba","bad","d","da","dad","m","ma","mad"]
    terminals
    ["bad","dad","mad"]
    outcomes
    [null,null,null,false]
    stack
    [{"prefix":"m","index":1},{"prefix":"d","index":1},{"prefix":"ba","index":2}]
    operationIndex
    4
    phase
    "literal"
    operation
    "search"
    pattern
    ".ad"
    prefix
    "b"
    current
    {"prefix":"b","index":1}
  20. Process one candidate prefix at its consumed pattern depth.

    A complete consumed pattern succeeds only at a terminal node. Reverse child pushing yields illustrative a-first DFS; pending alternatives are abandoned on early success.

    paths
    ["","b","ba","bad","d","da","dad","m","ma","mad"]
    terminals
    ["bad","dad","mad"]
    outcomes
    [null,null,null,false]
    stack
    [{"prefix":"m","index":1},{"prefix":"d","index":1},{"prefix":"bad","index":3}]
    operationIndex
    4
    phase
    "literal"
    operation
    "search"
    pattern
    ".ad"
    prefix
    "ba"
    current
    {"prefix":"ba","index":2}
  21. Process one candidate prefix at its consumed pattern depth.

    A complete consumed pattern succeeds only at a terminal node. Reverse child pushing yields illustrative a-first DFS; pending alternatives are abandoned on early success.

    paths
    ["","b","ba","bad","d","da","dad","m","ma","mad"]
    terminals
    ["bad","dad","mad"]
    outcomes
    [null,null,null,false]
    stack
    [{"prefix":"m","index":1},{"prefix":"d","index":1}]
    operationIndex
    4
    phase
    "accept"
    operation
    "search"
    pattern
    ".ad"
    prefix
    "bad"
    current
    {"prefix":"bad","index":3}
  22. Complete the boolean query without changing the dictionary.

    Outstanding alternative frames, if any, belong to this finished query and are discarded before the next call.

    paths
    ["","b","ba","bad","d","da","dad","m","ma","mad"]
    terminals
    ["bad","dad","mad"]
    outcomes
    [null,null,null,false,true]
    stack
    [{"prefix":"m","index":1},{"prefix":"d","index":1}]
    operationIndex
    4
    phase
    "search-result"
    operation
    "search"
    pattern
    ".ad"
    prefix
    null
    answer
    true
  23. Begin a read-only exact-length pattern search.

    Stack top is at the right. A dot consumes exactly one letter; query frames may allocate, but trie nodes and terminal flags never change.

    paths
    ["","b","ba","bad","d","da","dad","m","ma","mad"]
    terminals
    ["bad","dad","mad"]
    outcomes
    [null,null,null,false,true]
    stack
    [{"prefix":"","index":0}]
    operationIndex
    5
    phase
    "search-start"
    operation
    "search"
    pattern
    "ba"
    prefix
    null
  24. Process one candidate prefix at its consumed pattern depth.

    A complete consumed pattern succeeds only at a terminal node. Reverse child pushing yields illustrative a-first DFS; pending alternatives are abandoned on early success.

    paths
    ["","b","ba","bad","d","da","dad","m","ma","mad"]
    terminals
    ["bad","dad","mad"]
    outcomes
    [null,null,null,false,true]
    stack
    [{"prefix":"b","index":1}]
    operationIndex
    5
    phase
    "literal"
    operation
    "search"
    pattern
    "ba"
    prefix
    ""
    current
    {"prefix":"","index":0}
  25. Process one candidate prefix at its consumed pattern depth.

    A complete consumed pattern succeeds only at a terminal node. Reverse child pushing yields illustrative a-first DFS; pending alternatives are abandoned on early success.

    paths
    ["","b","ba","bad","d","da","dad","m","ma","mad"]
    terminals
    ["bad","dad","mad"]
    outcomes
    [null,null,null,false,true]
    stack
    [{"prefix":"ba","index":2}]
    operationIndex
    5
    phase
    "literal"
    operation
    "search"
    pattern
    "ba"
    prefix
    "b"
    current
    {"prefix":"b","index":1}
  26. Process one candidate prefix at its consumed pattern depth.

    A complete consumed pattern succeeds only at a terminal node. Reverse child pushing yields illustrative a-first DFS; pending alternatives are abandoned on early success.

    paths
    ["","b","ba","bad","d","da","dad","m","ma","mad"]
    terminals
    ["bad","dad","mad"]
    outcomes
    [null,null,null,false,true]
    stack
    []
    operationIndex
    5
    phase
    "nonterminal"
    operation
    "search"
    pattern
    "ba"
    prefix
    "ba"
    current
    {"prefix":"ba","index":2}
  27. Complete the boolean query without changing the dictionary.

    Outstanding alternative frames, if any, belong to this finished query and are discarded before the next call.

    paths
    ["","b","ba","bad","d","da","dad","m","ma","mad"]
    terminals
    ["bad","dad","mad"]
    outcomes
    [null,null,null,false,true,false]
    stack
    []
    operationIndex
    5
    phase
    "search-result"
    operation
    "search"
    pattern
    "ba"
    prefix
    null
    answer
    false
  28. Follow or allocate one validated lowercase edge.

    All characters were validated before any trie mutation. Duplicate insertion reuses existing nodes.

    paths
    ["","b","ba","bad","d","da","dad","m","ma","mad"]
    terminals
    ["bad","dad","mad"]
    outcomes
    [null,null,null,false,true,false]
    stack
    []
    operationIndex
    6
    phase
    "add-edge"
    operation
    "add"
    prefix
    "b"
    allocated
    false
    word
    "ba"
    pattern
    null
  29. Follow or allocate one validated lowercase edge.

    All characters were validated before any trie mutation. Duplicate insertion reuses existing nodes.

    paths
    ["","b","ba","bad","d","da","dad","m","ma","mad"]
    terminals
    ["bad","dad","mad"]
    outcomes
    [null,null,null,false,true,false]
    stack
    []
    operationIndex
    6
    phase
    "add-edge"
    operation
    "add"
    prefix
    "ba"
    allocated
    false
    word
    "ba"
    pattern
    null
  30. Mark only the complete word terminal.

    null labels the void add outcome. Empty insertion marks the root; an existing longer path does not automatically mark its prefixes.

    paths
    ["","b","ba","bad","d","da","dad","m","ma","mad"]
    terminals
    ["ba","bad","dad","mad"]
    outcomes
    [null,null,null,false,true,false,null]
    stack
    []
    operationIndex
    6
    phase
    "add-terminal"
    operation
    "add"
    prefix
    "ba"
    word
    "ba"
    pattern
    null
  31. Begin a read-only exact-length pattern search.

    Stack top is at the right. A dot consumes exactly one letter; query frames may allocate, but trie nodes and terminal flags never change.

    paths
    ["","b","ba","bad","d","da","dad","m","ma","mad"]
    terminals
    ["ba","bad","dad","mad"]
    outcomes
    [null,null,null,false,true,false,null]
    stack
    [{"prefix":"","index":0}]
    operationIndex
    7
    phase
    "search-start"
    operation
    "search"
    pattern
    "ba"
    prefix
    null
  32. Process one candidate prefix at its consumed pattern depth.

    A complete consumed pattern succeeds only at a terminal node. Reverse child pushing yields illustrative a-first DFS; pending alternatives are abandoned on early success.

    paths
    ["","b","ba","bad","d","da","dad","m","ma","mad"]
    terminals
    ["ba","bad","dad","mad"]
    outcomes
    [null,null,null,false,true,false,null]
    stack
    [{"prefix":"b","index":1}]
    operationIndex
    7
    phase
    "literal"
    operation
    "search"
    pattern
    "ba"
    prefix
    ""
    current
    {"prefix":"","index":0}
  33. Process one candidate prefix at its consumed pattern depth.

    A complete consumed pattern succeeds only at a terminal node. Reverse child pushing yields illustrative a-first DFS; pending alternatives are abandoned on early success.

    paths
    ["","b","ba","bad","d","da","dad","m","ma","mad"]
    terminals
    ["ba","bad","dad","mad"]
    outcomes
    [null,null,null,false,true,false,null]
    stack
    [{"prefix":"ba","index":2}]
    operationIndex
    7
    phase
    "literal"
    operation
    "search"
    pattern
    "ba"
    prefix
    "b"
    current
    {"prefix":"b","index":1}
  34. Process one candidate prefix at its consumed pattern depth.

    A complete consumed pattern succeeds only at a terminal node. Reverse child pushing yields illustrative a-first DFS; pending alternatives are abandoned on early success.

    paths
    ["","b","ba","bad","d","da","dad","m","ma","mad"]
    terminals
    ["ba","bad","dad","mad"]
    outcomes
    [null,null,null,false,true,false,null]
    stack
    []
    operationIndex
    7
    phase
    "accept"
    operation
    "search"
    pattern
    "ba"
    prefix
    "ba"
    current
    {"prefix":"ba","index":2}
  35. Complete the boolean query without changing the dictionary.

    Outstanding alternative frames, if any, belong to this finished query and are discarded before the next call.

    paths
    ["","b","ba","bad","d","da","dad","m","ma","mad"]
    terminals
    ["ba","bad","dad","mad"]
    outcomes
    [null,null,null,false,true,false,null,true]
    stack
    []
    operationIndex
    7
    phase
    "search-result"
    operation
    "search"
    pattern
    "ba"
    prefix
    null
    answer
    true
  36. 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
    [null,null,null,false,true,false,null,true]

Empty word and duplicate insertion

Input: {"operations":[["search",""],["add",""],["search",""],["search","."],["add","a"],["add","a"],["search","."]]} · Operation outcomes: [false,null,true,false,null,null,true]

Step 1 of 20: Create an instance-owned empty trie.

The root path exists but is not terminal. Sorted path cards are a logical trie view, not child-array iteration or extra stored word strings.

Wildcard dictionary — consumed pattern depth and terminal words

Phase: initial.

Trie paths — sorted logical display

  • (root / empty path)prefix path only

Operation index: -1. Pattern: no active query.

Query candidates — stack top at right

Empty.

Completed operation outcomes — null means void add

Empty.

A dot consumes one edge. Complete pattern consumption still needs a terminal node. Pending alternatives at a successful query return are abandoned; they are not trie nodes and do not survive into the next call.

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
VariableValue
paths[""]
terminals[]
outcomes[]
stack[]
operationIndex-1
phase"initial"
prefix""
patternnull
See the affected Java block
 1 import java.util.*;
 2 public final class Solution {
 3     private static void validate(String text, boolean pattern) {
 4         Objects.requireNonNull(text,"text");
 5         for (int i = 0; i < text.length(); i++) {
 6             char c = text.charAt(i);
 7             if ((c < 'a' || c > 'z') && !(pattern && c == '.')) throw new IllegalArgumentException("expected lowercase ASCII" );
 8         }
 9     }
10     public static final class WordDictionary {
11         private static final class Node {
12             final Node[] children = new Node[26];
13             boolean terminal;
14         }
15         private record State(Node node, int index) {}
16         private final Node root = new Node();
17         public void add(String word) {
18             validate(word,false);
19             Node node = root;
20             for (int i = 0; i < word.length(); i++) {
21                 int slot = word.charAt(i)-'a';
22                 if (node.children[slot] == null) node.children[slot] = new Node();
23                 node = node.children[slot];
24             }
25             node.terminal = true;
26         }
27         public boolean search(String pattern) {
28             validate(pattern,true);
29             ArrayDeque<State> stack = new ArrayDeque<>();
30             stack.push(new State(root,0));
31             while (!stack.isEmpty()) {
32                 State state = stack.pop();
33                 if (state.index == pattern.length()) {
34                     if (state.node.terminal) return true;
35                     continue;
36                 }
37                 char c = pattern.charAt(state.index);
38                 if (c == '.') {
39                     for (int slot = 25; slot >= 0; slot--) if (state.node.children[slot] != null) stack.push(new State(state.node.children[slot],state.index+1));
40                 } else {
41                     Node child = state.node.children[c-'a'];
42                     if (child != null) stack.push(new State(child,state.index+1));
43                 }
44             }
45             return false;
46         }
47     }
48     public static final class Baseline {
49         private final Set<String> words = new HashSet<>();
50         public void add(String word) { validate(word,false); words.add(word); }
51         public boolean search(String pattern) {
52             validate(pattern,true);
53             for (String word : words) {
54                 if (word.length() != pattern.length()) continue;
55                 boolean matches = true;
56                 for (int i = 0; i < word.length(); i++) if (pattern.charAt(i) != '.' && pattern.charAt(i) != word.charAt(i)) { matches = false; break; }
57                 if (matches) return true;
58             }
59             return false;
60         }
61     }
62 }
63

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

Read the full static trace
  1. Create an instance-owned empty trie.

    The root path exists but is not terminal. Sorted path cards are a logical trie view, not child-array iteration or extra stored word strings.

    paths
    [""]
    terminals
    []
    outcomes
    []
    stack
    []
    operationIndex
    -1
    phase
    "initial"
    prefix
    ""
    pattern
    null
  2. Begin a read-only exact-length pattern search.

    Stack top is at the right. A dot consumes exactly one letter; query frames may allocate, but trie nodes and terminal flags never change.

    paths
    [""]
    terminals
    []
    outcomes
    []
    stack
    [{"prefix":"","index":0}]
    operationIndex
    0
    phase
    "search-start"
    operation
    "search"
    pattern
    ""
    prefix
    null
  3. Process one candidate prefix at its consumed pattern depth.

    A complete consumed pattern succeeds only at a terminal node. Reverse child pushing yields illustrative a-first DFS; pending alternatives are abandoned on early success.

    paths
    [""]
    terminals
    []
    outcomes
    []
    stack
    []
    operationIndex
    0
    phase
    "nonterminal"
    operation
    "search"
    pattern
    ""
    prefix
    ""
    current
    {"prefix":"","index":0}
  4. Complete the boolean query without changing the dictionary.

    Outstanding alternative frames, if any, belong to this finished query and are discarded before the next call.

    paths
    [""]
    terminals
    []
    outcomes
    [false]
    stack
    []
    operationIndex
    0
    phase
    "search-result"
    operation
    "search"
    pattern
    ""
    prefix
    null
    answer
    false
  5. Mark only the complete word terminal.

    null labels the void add outcome. Empty insertion marks the root; an existing longer path does not automatically mark its prefixes.

    paths
    [""]
    terminals
    [""]
    outcomes
    [false,null]
    stack
    []
    operationIndex
    1
    phase
    "add-terminal"
    operation
    "add"
    prefix
    ""
    word
    ""
    pattern
    null
  6. Begin a read-only exact-length pattern search.

    Stack top is at the right. A dot consumes exactly one letter; query frames may allocate, but trie nodes and terminal flags never change.

    paths
    [""]
    terminals
    [""]
    outcomes
    [false,null]
    stack
    [{"prefix":"","index":0}]
    operationIndex
    2
    phase
    "search-start"
    operation
    "search"
    pattern
    ""
    prefix
    null
  7. Process one candidate prefix at its consumed pattern depth.

    A complete consumed pattern succeeds only at a terminal node. Reverse child pushing yields illustrative a-first DFS; pending alternatives are abandoned on early success.

    paths
    [""]
    terminals
    [""]
    outcomes
    [false,null]
    stack
    []
    operationIndex
    2
    phase
    "accept"
    operation
    "search"
    pattern
    ""
    prefix
    ""
    current
    {"prefix":"","index":0}
  8. Complete the boolean query without changing the dictionary.

    Outstanding alternative frames, if any, belong to this finished query and are discarded before the next call.

    paths
    [""]
    terminals
    [""]
    outcomes
    [false,null,true]
    stack
    []
    operationIndex
    2
    phase
    "search-result"
    operation
    "search"
    pattern
    ""
    prefix
    null
    answer
    true
  9. Begin a read-only exact-length pattern search.

    Stack top is at the right. A dot consumes exactly one letter; query frames may allocate, but trie nodes and terminal flags never change.

    paths
    [""]
    terminals
    [""]
    outcomes
    [false,null,true]
    stack
    [{"prefix":"","index":0}]
    operationIndex
    3
    phase
    "search-start"
    operation
    "search"
    pattern
    "."
    prefix
    null
  10. Process one candidate prefix at its consumed pattern depth.

    A complete consumed pattern succeeds only at a terminal node. Reverse child pushing yields illustrative a-first DFS; pending alternatives are abandoned on early success.

    paths
    [""]
    terminals
    [""]
    outcomes
    [false,null,true]
    stack
    []
    operationIndex
    3
    phase
    "branch"
    operation
    "search"
    pattern
    "."
    prefix
    ""
    current
    {"prefix":"","index":0}
  11. Complete the boolean query without changing the dictionary.

    Outstanding alternative frames, if any, belong to this finished query and are discarded before the next call.

    paths
    [""]
    terminals
    [""]
    outcomes
    [false,null,true,false]
    stack
    []
    operationIndex
    3
    phase
    "search-result"
    operation
    "search"
    pattern
    "."
    prefix
    null
    answer
    false
  12. Follow or allocate one validated lowercase edge.

    All characters were validated before any trie mutation. Duplicate insertion reuses existing nodes.

    paths
    ["","a"]
    terminals
    [""]
    outcomes
    [false,null,true,false]
    stack
    []
    operationIndex
    4
    phase
    "add-edge"
    operation
    "add"
    prefix
    "a"
    allocated
    true
    word
    "a"
    pattern
    null
  13. Mark only the complete word terminal.

    null labels the void add outcome. Empty insertion marks the root; an existing longer path does not automatically mark its prefixes.

    paths
    ["","a"]
    terminals
    ["","a"]
    outcomes
    [false,null,true,false,null]
    stack
    []
    operationIndex
    4
    phase
    "add-terminal"
    operation
    "add"
    prefix
    "a"
    word
    "a"
    pattern
    null
  14. Follow or allocate one validated lowercase edge.

    All characters were validated before any trie mutation. Duplicate insertion reuses existing nodes.

    paths
    ["","a"]
    terminals
    ["","a"]
    outcomes
    [false,null,true,false,null]
    stack
    []
    operationIndex
    5
    phase
    "add-edge"
    operation
    "add"
    prefix
    "a"
    allocated
    false
    word
    "a"
    pattern
    null
  15. Mark only the complete word terminal.

    null labels the void add outcome. Empty insertion marks the root; an existing longer path does not automatically mark its prefixes.

    paths
    ["","a"]
    terminals
    ["","a"]
    outcomes
    [false,null,true,false,null,null]
    stack
    []
    operationIndex
    5
    phase
    "add-terminal"
    operation
    "add"
    prefix
    "a"
    word
    "a"
    pattern
    null
  16. Begin a read-only exact-length pattern search.

    Stack top is at the right. A dot consumes exactly one letter; query frames may allocate, but trie nodes and terminal flags never change.

    paths
    ["","a"]
    terminals
    ["","a"]
    outcomes
    [false,null,true,false,null,null]
    stack
    [{"prefix":"","index":0}]
    operationIndex
    6
    phase
    "search-start"
    operation
    "search"
    pattern
    "."
    prefix
    null
  17. Process one candidate prefix at its consumed pattern depth.

    A complete consumed pattern succeeds only at a terminal node. Reverse child pushing yields illustrative a-first DFS; pending alternatives are abandoned on early success.

    paths
    ["","a"]
    terminals
    ["","a"]
    outcomes
    [false,null,true,false,null,null]
    stack
    [{"prefix":"a","index":1}]
    operationIndex
    6
    phase
    "branch"
    operation
    "search"
    pattern
    "."
    prefix
    ""
    current
    {"prefix":"","index":0}
  18. Process one candidate prefix at its consumed pattern depth.

    A complete consumed pattern succeeds only at a terminal node. Reverse child pushing yields illustrative a-first DFS; pending alternatives are abandoned on early success.

    paths
    ["","a"]
    terminals
    ["","a"]
    outcomes
    [false,null,true,false,null,null]
    stack
    []
    operationIndex
    6
    phase
    "accept"
    operation
    "search"
    pattern
    "."
    prefix
    "a"
    current
    {"prefix":"a","index":1}
  19. Complete the boolean query without changing the dictionary.

    Outstanding alternative frames, if any, belong to this finished query and are discarded before the next call.

    paths
    ["","a"]
    terminals
    ["","a"]
    outcomes
    [false,null,true,false,null,null,true]
    stack
    []
    operationIndex
    6
    phase
    "search-result"
    operation
    "search"
    pattern
    "."
    prefix
    null
    answer
    true
  20. 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
    [false,null,true,false,null,null,true]

Pending wildcard alternatives can be abandoned on success

Input: {"operations":[["add","ab"],["add","ac"],["search","a."],["search","..."],["search",".b"]]} · Operation outcomes: [null,null,true,false,true]

Step 1 of 24: Create an instance-owned empty trie.

The root path exists but is not terminal. Sorted path cards are a logical trie view, not child-array iteration or extra stored word strings.

Wildcard dictionary — consumed pattern depth and terminal words

Phase: initial.

Trie paths — sorted logical display

  • (root / empty path)prefix path only

Operation index: -1. Pattern: no active query.

Query candidates — stack top at right

Empty.

Completed operation outcomes — null means void add

Empty.

A dot consumes one edge. Complete pattern consumption still needs a terminal node. Pending alternatives at a successful query return are abandoned; they are not trie nodes and do not survive into the next call.

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
VariableValue
paths[""]
terminals[]
outcomes[]
stack[]
operationIndex-1
phase"initial"
prefix""
patternnull
See the affected Java block
 1 import java.util.*;
 2 public final class Solution {
 3     private static void validate(String text, boolean pattern) {
 4         Objects.requireNonNull(text,"text");
 5         for (int i = 0; i < text.length(); i++) {
 6             char c = text.charAt(i);
 7             if ((c < 'a' || c > 'z') && !(pattern && c == '.')) throw new IllegalArgumentException("expected lowercase ASCII" );
 8         }
 9     }
10     public static final class WordDictionary {
11         private static final class Node {
12             final Node[] children = new Node[26];
13             boolean terminal;
14         }
15         private record State(Node node, int index) {}
16         private final Node root = new Node();
17         public void add(String word) {
18             validate(word,false);
19             Node node = root;
20             for (int i = 0; i < word.length(); i++) {
21                 int slot = word.charAt(i)-'a';
22                 if (node.children[slot] == null) node.children[slot] = new Node();
23                 node = node.children[slot];
24             }
25             node.terminal = true;
26         }
27         public boolean search(String pattern) {
28             validate(pattern,true);
29             ArrayDeque<State> stack = new ArrayDeque<>();
30             stack.push(new State(root,0));
31             while (!stack.isEmpty()) {
32                 State state = stack.pop();
33                 if (state.index == pattern.length()) {
34                     if (state.node.terminal) return true;
35                     continue;
36                 }
37                 char c = pattern.charAt(state.index);
38                 if (c == '.') {
39                     for (int slot = 25; slot >= 0; slot--) if (state.node.children[slot] != null) stack.push(new State(state.node.children[slot],state.index+1));
40                 } else {
41                     Node child = state.node.children[c-'a'];
42                     if (child != null) stack.push(new State(child,state.index+1));
43                 }
44             }
45             return false;
46         }
47     }
48     public static final class Baseline {
49         private final Set<String> words = new HashSet<>();
50         public void add(String word) { validate(word,false); words.add(word); }
51         public boolean search(String pattern) {
52             validate(pattern,true);
53             for (String word : words) {
54                 if (word.length() != pattern.length()) continue;
55                 boolean matches = true;
56                 for (int i = 0; i < word.length(); i++) if (pattern.charAt(i) != '.' && pattern.charAt(i) != word.charAt(i)) { matches = false; break; }
57                 if (matches) return true;
58             }
59             return false;
60         }
61     }
62 }
63

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

Read the full static trace
  1. Create an instance-owned empty trie.

    The root path exists but is not terminal. Sorted path cards are a logical trie view, not child-array iteration or extra stored word strings.

    paths
    [""]
    terminals
    []
    outcomes
    []
    stack
    []
    operationIndex
    -1
    phase
    "initial"
    prefix
    ""
    pattern
    null
  2. Follow or allocate one validated lowercase edge.

    All characters were validated before any trie mutation. Duplicate insertion reuses existing nodes.

    paths
    ["","a"]
    terminals
    []
    outcomes
    []
    stack
    []
    operationIndex
    0
    phase
    "add-edge"
    operation
    "add"
    prefix
    "a"
    allocated
    true
    word
    "ab"
    pattern
    null
  3. Follow or allocate one validated lowercase edge.

    All characters were validated before any trie mutation. Duplicate insertion reuses existing nodes.

    paths
    ["","a","ab"]
    terminals
    []
    outcomes
    []
    stack
    []
    operationIndex
    0
    phase
    "add-edge"
    operation
    "add"
    prefix
    "ab"
    allocated
    true
    word
    "ab"
    pattern
    null
  4. Mark only the complete word terminal.

    null labels the void add outcome. Empty insertion marks the root; an existing longer path does not automatically mark its prefixes.

    paths
    ["","a","ab"]
    terminals
    ["ab"]
    outcomes
    [null]
    stack
    []
    operationIndex
    0
    phase
    "add-terminal"
    operation
    "add"
    prefix
    "ab"
    word
    "ab"
    pattern
    null
  5. Follow or allocate one validated lowercase edge.

    All characters were validated before any trie mutation. Duplicate insertion reuses existing nodes.

    paths
    ["","a","ab"]
    terminals
    ["ab"]
    outcomes
    [null]
    stack
    []
    operationIndex
    1
    phase
    "add-edge"
    operation
    "add"
    prefix
    "a"
    allocated
    false
    word
    "ac"
    pattern
    null
  6. Follow or allocate one validated lowercase edge.

    All characters were validated before any trie mutation. Duplicate insertion reuses existing nodes.

    paths
    ["","a","ab","ac"]
    terminals
    ["ab"]
    outcomes
    [null]
    stack
    []
    operationIndex
    1
    phase
    "add-edge"
    operation
    "add"
    prefix
    "ac"
    allocated
    true
    word
    "ac"
    pattern
    null
  7. Mark only the complete word terminal.

    null labels the void add outcome. Empty insertion marks the root; an existing longer path does not automatically mark its prefixes.

    paths
    ["","a","ab","ac"]
    terminals
    ["ab","ac"]
    outcomes
    [null,null]
    stack
    []
    operationIndex
    1
    phase
    "add-terminal"
    operation
    "add"
    prefix
    "ac"
    word
    "ac"
    pattern
    null
  8. Begin a read-only exact-length pattern search.

    Stack top is at the right. A dot consumes exactly one letter; query frames may allocate, but trie nodes and terminal flags never change.

    paths
    ["","a","ab","ac"]
    terminals
    ["ab","ac"]
    outcomes
    [null,null]
    stack
    [{"prefix":"","index":0}]
    operationIndex
    2
    phase
    "search-start"
    operation
    "search"
    pattern
    "a."
    prefix
    null
  9. Process one candidate prefix at its consumed pattern depth.

    A complete consumed pattern succeeds only at a terminal node. Reverse child pushing yields illustrative a-first DFS; pending alternatives are abandoned on early success.

    paths
    ["","a","ab","ac"]
    terminals
    ["ab","ac"]
    outcomes
    [null,null]
    stack
    [{"prefix":"a","index":1}]
    operationIndex
    2
    phase
    "literal"
    operation
    "search"
    pattern
    "a."
    prefix
    ""
    current
    {"prefix":"","index":0}
  10. Process one candidate prefix at its consumed pattern depth.

    A complete consumed pattern succeeds only at a terminal node. Reverse child pushing yields illustrative a-first DFS; pending alternatives are abandoned on early success.

    paths
    ["","a","ab","ac"]
    terminals
    ["ab","ac"]
    outcomes
    [null,null]
    stack
    [{"prefix":"ac","index":2},{"prefix":"ab","index":2}]
    operationIndex
    2
    phase
    "branch"
    operation
    "search"
    pattern
    "a."
    prefix
    "a"
    current
    {"prefix":"a","index":1}
  11. Process one candidate prefix at its consumed pattern depth.

    A complete consumed pattern succeeds only at a terminal node. Reverse child pushing yields illustrative a-first DFS; pending alternatives are abandoned on early success.

    paths
    ["","a","ab","ac"]
    terminals
    ["ab","ac"]
    outcomes
    [null,null]
    stack
    [{"prefix":"ac","index":2}]
    operationIndex
    2
    phase
    "accept"
    operation
    "search"
    pattern
    "a."
    prefix
    "ab"
    current
    {"prefix":"ab","index":2}
  12. Complete the boolean query without changing the dictionary.

    Outstanding alternative frames, if any, belong to this finished query and are discarded before the next call.

    paths
    ["","a","ab","ac"]
    terminals
    ["ab","ac"]
    outcomes
    [null,null,true]
    stack
    [{"prefix":"ac","index":2}]
    operationIndex
    2
    phase
    "search-result"
    operation
    "search"
    pattern
    "a."
    prefix
    null
    answer
    true
  13. Begin a read-only exact-length pattern search.

    Stack top is at the right. A dot consumes exactly one letter; query frames may allocate, but trie nodes and terminal flags never change.

    paths
    ["","a","ab","ac"]
    terminals
    ["ab","ac"]
    outcomes
    [null,null,true]
    stack
    [{"prefix":"","index":0}]
    operationIndex
    3
    phase
    "search-start"
    operation
    "search"
    pattern
    "..."
    prefix
    null
  14. Process one candidate prefix at its consumed pattern depth.

    A complete consumed pattern succeeds only at a terminal node. Reverse child pushing yields illustrative a-first DFS; pending alternatives are abandoned on early success.

    paths
    ["","a","ab","ac"]
    terminals
    ["ab","ac"]
    outcomes
    [null,null,true]
    stack
    [{"prefix":"a","index":1}]
    operationIndex
    3
    phase
    "branch"
    operation
    "search"
    pattern
    "..."
    prefix
    ""
    current
    {"prefix":"","index":0}
  15. Process one candidate prefix at its consumed pattern depth.

    A complete consumed pattern succeeds only at a terminal node. Reverse child pushing yields illustrative a-first DFS; pending alternatives are abandoned on early success.

    paths
    ["","a","ab","ac"]
    terminals
    ["ab","ac"]
    outcomes
    [null,null,true]
    stack
    [{"prefix":"ac","index":2},{"prefix":"ab","index":2}]
    operationIndex
    3
    phase
    "branch"
    operation
    "search"
    pattern
    "..."
    prefix
    "a"
    current
    {"prefix":"a","index":1}
  16. Process one candidate prefix at its consumed pattern depth.

    A complete consumed pattern succeeds only at a terminal node. Reverse child pushing yields illustrative a-first DFS; pending alternatives are abandoned on early success.

    paths
    ["","a","ab","ac"]
    terminals
    ["ab","ac"]
    outcomes
    [null,null,true]
    stack
    [{"prefix":"ac","index":2}]
    operationIndex
    3
    phase
    "branch"
    operation
    "search"
    pattern
    "..."
    prefix
    "ab"
    current
    {"prefix":"ab","index":2}
  17. Process one candidate prefix at its consumed pattern depth.

    A complete consumed pattern succeeds only at a terminal node. Reverse child pushing yields illustrative a-first DFS; pending alternatives are abandoned on early success.

    paths
    ["","a","ab","ac"]
    terminals
    ["ab","ac"]
    outcomes
    [null,null,true]
    stack
    []
    operationIndex
    3
    phase
    "branch"
    operation
    "search"
    pattern
    "..."
    prefix
    "ac"
    current
    {"prefix":"ac","index":2}
  18. Complete the boolean query without changing the dictionary.

    Outstanding alternative frames, if any, belong to this finished query and are discarded before the next call.

    paths
    ["","a","ab","ac"]
    terminals
    ["ab","ac"]
    outcomes
    [null,null,true,false]
    stack
    []
    operationIndex
    3
    phase
    "search-result"
    operation
    "search"
    pattern
    "..."
    prefix
    null
    answer
    false
  19. Begin a read-only exact-length pattern search.

    Stack top is at the right. A dot consumes exactly one letter; query frames may allocate, but trie nodes and terminal flags never change.

    paths
    ["","a","ab","ac"]
    terminals
    ["ab","ac"]
    outcomes
    [null,null,true,false]
    stack
    [{"prefix":"","index":0}]
    operationIndex
    4
    phase
    "search-start"
    operation
    "search"
    pattern
    ".b"
    prefix
    null
  20. Process one candidate prefix at its consumed pattern depth.

    A complete consumed pattern succeeds only at a terminal node. Reverse child pushing yields illustrative a-first DFS; pending alternatives are abandoned on early success.

    paths
    ["","a","ab","ac"]
    terminals
    ["ab","ac"]
    outcomes
    [null,null,true,false]
    stack
    [{"prefix":"a","index":1}]
    operationIndex
    4
    phase
    "branch"
    operation
    "search"
    pattern
    ".b"
    prefix
    ""
    current
    {"prefix":"","index":0}
  21. Process one candidate prefix at its consumed pattern depth.

    A complete consumed pattern succeeds only at a terminal node. Reverse child pushing yields illustrative a-first DFS; pending alternatives are abandoned on early success.

    paths
    ["","a","ab","ac"]
    terminals
    ["ab","ac"]
    outcomes
    [null,null,true,false]
    stack
    [{"prefix":"ab","index":2}]
    operationIndex
    4
    phase
    "literal"
    operation
    "search"
    pattern
    ".b"
    prefix
    "a"
    current
    {"prefix":"a","index":1}
  22. Process one candidate prefix at its consumed pattern depth.

    A complete consumed pattern succeeds only at a terminal node. Reverse child pushing yields illustrative a-first DFS; pending alternatives are abandoned on early success.

    paths
    ["","a","ab","ac"]
    terminals
    ["ab","ac"]
    outcomes
    [null,null,true,false]
    stack
    []
    operationIndex
    4
    phase
    "accept"
    operation
    "search"
    pattern
    ".b"
    prefix
    "ab"
    current
    {"prefix":"ab","index":2}
  23. Complete the boolean query without changing the dictionary.

    Outstanding alternative frames, if any, belong to this finished query and are discarded before the next call.

    paths
    ["","a","ab","ac"]
    terminals
    ["ab","ac"]
    outcomes
    [null,null,true,false,true]
    stack
    []
    operationIndex
    4
    phase
    "search-result"
    operation
    "search"
    pattern
    ".b"
    prefix
    null
    answer
    true
  24. 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
    [null,null,true,false,true]

No invented edges during failed queries

Input: {"operations":[["search","."],["search",""]]} · Operation outcomes: [false,false]

Step 1 of 8: Create an instance-owned empty trie.

The root path exists but is not terminal. Sorted path cards are a logical trie view, not child-array iteration or extra stored word strings.

Wildcard dictionary — consumed pattern depth and terminal words

Phase: initial.

Trie paths — sorted logical display

  • (root / empty path)prefix path only

Operation index: -1. Pattern: no active query.

Query candidates — stack top at right

Empty.

Completed operation outcomes — null means void add

Empty.

A dot consumes one edge. Complete pattern consumption still needs a terminal node. Pending alternatives at a successful query return are abandoned; they are not trie nodes and do not survive into the next call.

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
VariableValue
paths[""]
terminals[]
outcomes[]
stack[]
operationIndex-1
phase"initial"
prefix""
patternnull
See the affected Java block
 1 import java.util.*;
 2 public final class Solution {
 3     private static void validate(String text, boolean pattern) {
 4         Objects.requireNonNull(text,"text");
 5         for (int i = 0; i < text.length(); i++) {
 6             char c = text.charAt(i);
 7             if ((c < 'a' || c > 'z') && !(pattern && c == '.')) throw new IllegalArgumentException("expected lowercase ASCII" );
 8         }
 9     }
10     public static final class WordDictionary {
11         private static final class Node {
12             final Node[] children = new Node[26];
13             boolean terminal;
14         }
15         private record State(Node node, int index) {}
16         private final Node root = new Node();
17         public void add(String word) {
18             validate(word,false);
19             Node node = root;
20             for (int i = 0; i < word.length(); i++) {
21                 int slot = word.charAt(i)-'a';
22                 if (node.children[slot] == null) node.children[slot] = new Node();
23                 node = node.children[slot];
24             }
25             node.terminal = true;
26         }
27         public boolean search(String pattern) {
28             validate(pattern,true);
29             ArrayDeque<State> stack = new ArrayDeque<>();
30             stack.push(new State(root,0));
31             while (!stack.isEmpty()) {
32                 State state = stack.pop();
33                 if (state.index == pattern.length()) {
34                     if (state.node.terminal) return true;
35                     continue;
36                 }
37                 char c = pattern.charAt(state.index);
38                 if (c == '.') {
39                     for (int slot = 25; slot >= 0; slot--) if (state.node.children[slot] != null) stack.push(new State(state.node.children[slot],state.index+1));
40                 } else {
41                     Node child = state.node.children[c-'a'];
42                     if (child != null) stack.push(new State(child,state.index+1));
43                 }
44             }
45             return false;
46         }
47     }
48     public static final class Baseline {
49         private final Set<String> words = new HashSet<>();
50         public void add(String word) { validate(word,false); words.add(word); }
51         public boolean search(String pattern) {
52             validate(pattern,true);
53             for (String word : words) {
54                 if (word.length() != pattern.length()) continue;
55                 boolean matches = true;
56                 for (int i = 0; i < word.length(); i++) if (pattern.charAt(i) != '.' && pattern.charAt(i) != word.charAt(i)) { matches = false; break; }
57                 if (matches) return true;
58             }
59             return false;
60         }
61     }
62 }
63

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

Read the full static trace
  1. Create an instance-owned empty trie.

    The root path exists but is not terminal. Sorted path cards are a logical trie view, not child-array iteration or extra stored word strings.

    paths
    [""]
    terminals
    []
    outcomes
    []
    stack
    []
    operationIndex
    -1
    phase
    "initial"
    prefix
    ""
    pattern
    null
  2. Begin a read-only exact-length pattern search.

    Stack top is at the right. A dot consumes exactly one letter; query frames may allocate, but trie nodes and terminal flags never change.

    paths
    [""]
    terminals
    []
    outcomes
    []
    stack
    [{"prefix":"","index":0}]
    operationIndex
    0
    phase
    "search-start"
    operation
    "search"
    pattern
    "."
    prefix
    null
  3. Process one candidate prefix at its consumed pattern depth.

    A complete consumed pattern succeeds only at a terminal node. Reverse child pushing yields illustrative a-first DFS; pending alternatives are abandoned on early success.

    paths
    [""]
    terminals
    []
    outcomes
    []
    stack
    []
    operationIndex
    0
    phase
    "branch"
    operation
    "search"
    pattern
    "."
    prefix
    ""
    current
    {"prefix":"","index":0}
  4. Complete the boolean query without changing the dictionary.

    Outstanding alternative frames, if any, belong to this finished query and are discarded before the next call.

    paths
    [""]
    terminals
    []
    outcomes
    [false]
    stack
    []
    operationIndex
    0
    phase
    "search-result"
    operation
    "search"
    pattern
    "."
    prefix
    null
    answer
    false
  5. Begin a read-only exact-length pattern search.

    Stack top is at the right. A dot consumes exactly one letter; query frames may allocate, but trie nodes and terminal flags never change.

    paths
    [""]
    terminals
    []
    outcomes
    [false]
    stack
    [{"prefix":"","index":0}]
    operationIndex
    1
    phase
    "search-start"
    operation
    "search"
    pattern
    ""
    prefix
    null
  6. Process one candidate prefix at its consumed pattern depth.

    A complete consumed pattern succeeds only at a terminal node. Reverse child pushing yields illustrative a-first DFS; pending alternatives are abandoned on early success.

    paths
    [""]
    terminals
    []
    outcomes
    [false]
    stack
    []
    operationIndex
    1
    phase
    "nonterminal"
    operation
    "search"
    pattern
    ""
    prefix
    ""
    current
    {"prefix":"","index":0}
  7. Complete the boolean query without changing the dictionary.

    Outstanding alternative frames, if any, belong to this finished query and are discarded before the next call.

    paths
    [""]
    terminals
    []
    outcomes
    [false,false]
    stack
    []
    operationIndex
    1
    phase
    "search-result"
    operation
    "search"
    pattern
    ""
    prefix
    null
    answer
    false
  8. 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
    [false,false]

Test the contract

  1. Input: Fresh dictionary; search empty
    Output: false

    Root exists but is not terminal.

  2. Input: add empty twice; search empty
    Output: true

    Idempotent root terminal.

  3. Input: Shared prefixes and branching dot suffixes
    Output: exact full-length boolean

    All alternatives and terminal state checked.

  4. Input: Rejected late character in add
    Output: exception with unchanged graph

    Validation precedes mutation.

  5. Input: 10,000-letter word and dot pattern
    Output: true without recursive-stack dependence

    Explicit depth frontier.

Common mistakes and counterexamples

Accept a path when the pattern ends

Counterexample: add bad does not make search ba true.

Require terminal at exactly the exhausted pattern length.

Treat dot like a star

Counterexample: Pattern b. must not match bad or b.

Consume exactly one edge per dot.

Explore only the first wildcard child

Counterexample: The first branch may fail while another has a matching suffix.

Retain all existing alternatives until one succeeds or all fail.

Validate while adding characters

Counterexample: add az? could allocate az before throwing.

Validate the whole word first and verify graph preservation on rejected adds.

Follow-ups

Return a matching word.

Specify a tie rule, such as lexicographically smallest. The current a-first traversal can reconstruct that witness, but paths/output allocation and early-return ordering must become contractual.

Add a star matching any number of letters.

The state graph now has zero-consumption and repeated-consumption transitions. Use memoized (node,patternIndex) reasoning and define the pattern grammar; this is a different algorithm.

Support deletion or concurrent access.

Deletion must preserve shared prefixes and clear only the requested terminal; pruning needs ownership/count metadata. Concurrent mutation requires synchronization or immutable snapshots so searches do not observe partial updates.

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.

No unsaved text changes · 192/20,000 characters

Self-review

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 equivalence claims.