28.04Intermediate / Advanced4 topics15 min4 interactive animations

Wildcard searches

Searching a trie with patterns: '.' wildcards, prefix-and-suffix filters, depth-first enumeration, and Word Search II, where the trie prunes a board search.

Learning goals

Collect all words that match a pattern with dots
Answer prefix-and-suffix queries with a single trie lookup
Enumerate a trie depth-first with an explicit stack
Use a trie to prune the DFS in Word Search II

Prerequisites

Prefix problemsRecursion and backtrackingGrid search

Crossword helpers match 'c.t' against a dictionary, and a word-game solver tries every path on a board. Both look at far too many candidates unless the trie says 'no word continues this way' as early as possible.

28.04.1

Dot wildcard

Where the dictionary lesson asked 'is there any match?', this version collects every match. The recursion carries the path built so far: a letter extends it by one edge, a dot extends it along each child in turn, and reaching the end of the pattern at a word end adds the path to the result. Words come out in alphabetical order because the children are visited in letter order.

The cost depends on the pattern. A pattern with no dots follows one path. A pattern of m dots can visit every node at depth m, which is why the search is O(nodes) in the worst case. Replacing the leading letters of a pattern by dots makes the search wider; keep real letters early in the pattern when you can.

Java

1class PatternTrie {
2    private static class Node {
3        Node[] next = new Node[26];
4        boolean end;
5    }
6    private final Node root = new Node();
7    void add(String word) {
8        Node n = root;
9        for (char c : word.toCharArray()) {
10            int i = c - 'a';
11            if (n.next[i] == null) n.next[i] = new Node();
12            n = n.next[i];
13        }
14        n.end = true;
15    }
16    List<String> matches(String pattern) {
17        List<String> out = new ArrayList<>();
18        walk(root, pattern, 0, new StringBuilder(), out);
19        return out;
20    }
21    private void walk(Node n, String p, int i, StringBuilder sb, List<String> out) {
22        if (n == null) return;
23        if (i == p.length()) { if (n.end) out.add(sb.toString()); return; }
24        char c = p.charAt(i);
25        for (int k = 0; k < 26; k++) {
26            if (n.next[k] == null || (c != '.' && c - 'a' != k)) continue;   // a letter keeps one branch
27            sb.append((char) ('a' + k));
28            walk(n.next[k], p, i + 1, sb, out);
29            sb.deleteCharAt(sb.length() - 1);
30        }
31    }
32}

Wildcards: '.' search by DFS, and the prefix + suffix filter

Interactive · edit the input

trie · 13 nodes

root

word

Being followedMatchDead endA word ends here

Setup

Search "b.d". A letter follows exactly one edge; a dot tries every child in turn, so the search becomes a DFS on the trie.

Step 1 / 7

Java

1boolean search(Node n, String p, int i) {               // does any word below n match p[i..]?
2    if (n == null) return false;
3    if (i == p.length()) return n.end;
4    char c = p.charAt(i);
5    if (c != '.') return search(n.next[c - 'a'], p, i + 1);   // a letter: one way only
6    for (Node child : n.next)                                  // a dot: try every branch
7        if (child != null && search(child, p, i + 1)) return true;
8    return false;
9}
10void addWord(String w) { for (int i = 0; i <= w.length(); i++) insert(w.substring(i) + "{" + w); }
11boolean hasPrefixSuffix(String pre, String suf) { return startsWith(suf + "{" + pre); }

Live state

0 nodes visited

pattern

"b.d"

No condition evaluated on this step

Execution trace (dry run table)Show 7 steps

Step	Line	State	What happens
1	L1	pattern="b.d"	Search "b.d". A letter follows exactly one edge; a dot tries every child in turn, so the search becomes a DFS on the trie.
2	L5	i=1 char=b	The letter 'b' leaves one way: follow it.
3	L6	i=1 char=.	A dot at position 1: try each of the 1 child in alphabetical order.
4	L7	i=2 branch=a	Try the branch 'a'.
5	L5	i=3 char=d	The letter 'd' leaves one way: follow it.
6	L3	i=3 end=true	The pattern is used up at a node where a word ends: match.
7	L7	return=true nodes visited=4	search("b.d") = true after 4 node visits. It stops at the first match.

28.04.2

Prefix/suffix filters

A filter such as a*e asks for words that start with a and end with e. A trie answers prefix questions only, so store each word under every suffix: for the word apple, insert apple{apple, pple{apple, ple{apple, le{apple, e{apple and {apple. The separator { sorts after z and never occurs in a word. The query pre*suf then becomes the prefix query suf{pre.

Choose the preset "Prefix + suffix" (a*e over apple apply ample): the animation lists every key and highlights those that start with e{a, which belong to apple and ample. The price is space: a word of length L adds L + 1 keys, so the trie can grow by about 1.5 × L² nodes per word. Store the index of the word at the end of each key to return the largest index, as the practice problem asks.

Java

1class WordFilter {
2    private static class Node {
3        Node[] next = new Node[27];             // 'a'..'z' and '{'
4        int index = -1;                          // the largest word index that passes through
5    }
6    private final Node root = new Node();
7    WordFilter(String[] words) {
8        for (int w = 0; w < words.length; w++) {
9            String word = words[w];
10            for (int i = 0; i <= word.length(); i++) insert(word.substring(i) + "{" + word, w);
11        }
12    }
13    private void insert(String key, int w) {
14        Node n = root;
15        for (char c : key.toCharArray()) {
16            int i = c - 'a';                     // '{' is 'a' + 26
17            if (n.next[i] == null) n.next[i] = new Node();
18            n = n.next[i];
19            n.index = w;                         // words are inserted in index order
20        }
21    }
22    int f(String prefix, String suffix) {        // largest index of a word with this prefix and suffix, or -1
23        Node n = root;
24        for (char c : (suffix + "{" + prefix).toCharArray()) {
25            n = n.next[c - 'a'];
26            if (n == null) return -1;
27        }
28        return n.index;
29    }
30}

Wildcards: '.' search by DFS, and the prefix + suffix filter

Interactive · edit the input

trie · 13 nodes

root

word

Being followedMatchDead endA word ends here

Setup

Search "b.d". A letter follows exactly one edge; a dot tries every child in turn, so the search becomes a DFS on the trie.

Step 1 / 7

Java

1boolean search(Node n, String p, int i) {               // does any word below n match p[i..]?
2    if (n == null) return false;
3    if (i == p.length()) return n.end;
4    char c = p.charAt(i);
5    if (c != '.') return search(n.next[c - 'a'], p, i + 1);   // a letter: one way only
6    for (Node child : n.next)                                  // a dot: try every branch
7        if (child != null && search(child, p, i + 1)) return true;
8    return false;
9}
10void addWord(String w) { for (int i = 0; i <= w.length(); i++) insert(w.substring(i) + "{" + w); }
11boolean hasPrefixSuffix(String pre, String suf) { return startsWith(suf + "{" + pre); }

Live state

0 nodes visited

pattern

"b.d"

No condition evaluated on this step

Execution trace (dry run table)Show 7 steps

Step	Line	State	What happens
1	L1	pattern="b.d"	Search "b.d". A letter follows exactly one edge; a dot tries every child in turn, so the search becomes a DFS on the trie.
2	L5	i=1 char=b	The letter 'b' leaves one way: follow it.
3	L6	i=1 char=.	A dot at position 1: try each of the 1 child in alphabetical order.
4	L7	i=2 branch=a	Try the branch 'a'.
5	L5	i=3 char=d	The letter 'd' leaves one way: follow it.
6	L3	i=3 end=true	The pattern is used up at a node where a word ends: match.
7	L7	return=true nodes visited=4	search("b.d") = true after 4 node visits. It stops at the first match.

28.04.3

DFS on trie

Every trie operation beyond a single path is a depth-first search: autocomplete, wildcards, counting words, finding the longest word. The recursive form is short, but an explicit stack avoids deep recursion and makes it easy to stop early. Push the root with an empty path; pop a node, report it if it ends a word, then push its children in reverse alphabetical order so that the smallest letter is popped first.

Pushing in reverse is the one trick: a stack pops the last item pushed, so to visit a before b you push b first. The stack holds at most one entry per child of the nodes on the current path, so its size is bounded by the depth times the alphabet.

Java

1class WordLister {
2    private static class Node {
3        Node[] next = new Node[26];
4        boolean end;
5    }
6    private final Node root = new Node();
7    void add(String word) {
8        Node n = root;
9        for (char c : word.toCharArray()) {
10            int i = c - 'a';
11            if (n.next[i] == null) n.next[i] = new Node();
12            n = n.next[i];
13        }
14        n.end = true;
15    }
16    List<String> allWords() {
17        List<String> out = new ArrayList<>();
18        Deque<Node> nodes = new ArrayDeque<>();
19        Deque<String> paths = new ArrayDeque<>();
20        nodes.push(root);
21        paths.push("");
22        while (!nodes.isEmpty()) {
23            Node n = nodes.pop();
24            String path = paths.pop();
25            if (n.end) out.add(path);
26            for (int c = 25; c >= 0; c--) {      // reverse order: the smallest letter is popped first
27                if (n.next[c] == null) continue;
28                nodes.push(n.next[c]);
29                paths.push(path + (char) ('a' + c));
30            }
31        }
32        return out;
33    }
34}

Wildcards: '.' search by DFS, and the prefix + suffix filter

Interactive · edit the input

trie · 13 nodes

root

word

Being followedMatchDead endA word ends here

Setup

Search "b.d". A letter follows exactly one edge; a dot tries every child in turn, so the search becomes a DFS on the trie.

Step 1 / 7

Java

1boolean search(Node n, String p, int i) {               // does any word below n match p[i..]?
2    if (n == null) return false;
3    if (i == p.length()) return n.end;
4    char c = p.charAt(i);
5    if (c != '.') return search(n.next[c - 'a'], p, i + 1);   // a letter: one way only
6    for (Node child : n.next)                                  // a dot: try every branch
7        if (child != null && search(child, p, i + 1)) return true;
8    return false;
9}
10void addWord(String w) { for (int i = 0; i <= w.length(); i++) insert(w.substring(i) + "{" + w); }
11boolean hasPrefixSuffix(String pre, String suf) { return startsWith(suf + "{" + pre); }

Live state

0 nodes visited

pattern

"b.d"

No condition evaluated on this step

Execution trace (dry run table)Show 7 steps

Step	Line	State	What happens
1	L1	pattern="b.d"	Search "b.d". A letter follows exactly one edge; a dot tries every child in turn, so the search becomes a DFS on the trie.
2	L5	i=1 char=b	The letter 'b' leaves one way: follow it.
3	L6	i=1 char=.	A dot at position 1: try each of the 1 child in alphabetical order.
4	L7	i=2 branch=a	Try the branch 'a'.
5	L5	i=3 char=d	The letter 'd' leaves one way: follow it.
6	L3	i=3 end=true	The pattern is used up at a node where a word ends: match.
7	L7	return=true nodes visited=4	search("b.d") = true after 4 node visits. It stops at the first match.

28.04.4

Word search II

Word Search II gives a letter board and a list of words and asks which words can be traced through adjacent cells without reusing a cell. Searching the board once per word repeats the same work for words that share a prefix. Instead put all the words in one trie and run a single DFS from every cell, moving in the trie at the same time: a branch is abandoned the moment the letters so far are not a prefix of any word.

The animation shows the board on top and the trie below. In the preset "Three words, one on the board" (oaa eta ihk with oath eat tea) the search enters 7 cells, cuts 20 branches whose letters continue no word, and finds only oath. Storing the finished word at its last node (instead of the end flag) avoids rebuilding the string, and the visited mark # is restored on the way back so other paths can use the cell.

Java

1class WordSearch2 {
2    private static class Node {
3        Node[] next = new Node[26];
4        String word;                             // the whole word, set at its last node
5    }
6    List<String> findWords(char[][] board, String[] words) {
7        Node root = new Node();
8        for (String w : words) {
9            Node n = root;
10            for (char c : w.toCharArray()) {
11                int i = c - 'a';
12                if (n.next[i] == null) n.next[i] = new Node();
13                n = n.next[i];
14            }
15            n.word = w;
16        }
17        Set<String> found = new TreeSet<>();
18        for (int r = 0; r < board.length; r++)
19            for (int c = 0; c < board[0].length; c++)
20                dfs(board, r, c, root, found);
21        return new ArrayList<>(found);
22    }
23    private void dfs(char[][] b, int r, int c, Node n, Set<String> found) {
24        if (r < 0 || c < 0 || r >= b.length || c >= b[0].length) return;
25        char ch = b[r][c];
26        if (ch == '#' || n.next[ch - 'a'] == null) return;   // used cell, or no word continues this way
27        n = n.next[ch - 'a'];
28        if (n.word != null) found.add(n.word);               // a word ends here
29        b[r][c] = '#';                                       // mark visited
30        dfs(b, r + 1, c, n, found); dfs(b, r - 1, c, n, found);
31        dfs(b, r, c + 1, n, found); dfs(b, r, c - 1, n, found);
32        b[r][c] = ch;                                        // restore
33    }
34}

Word Search II: DFS on a board guided by a trie

Interactive · edit the input

grid · 3 × 3

012

On the current pathCurrent cellWord foundA word ends here

trie of the words · 11 nodes

root

eat

oath

tea

On the current pathCurrent cellWord foundA word ends here

words found

none

Setup

All 3 words go into one trie. The board is searched once from every cell, and a branch is abandoned the moment the letters so far are not a prefix of any word.

Step 1 / 10

Java

1List<String> findWords(char[][] board, String[] words) {
2    Trie trie = new Trie(words);                          // all words in one trie, word stored at its last node
3    Set<String> found = new TreeSet<>();
4    for (int r = 0; r < board.length; r++)
5        for (int c = 0; c < board[0].length; c++)
6            dfs(board, r, c, trie.root, found);
7    return new ArrayList<>(found);
8}
9void dfs(char[][] b, int r, int c, Node n, Set<String> found) {
10    if (r < 0 || c < 0 || r >= b.length || c >= b[0].length) return;
11    char ch = b[r][c];
12    if (ch == '#' || n.next[ch - 'a'] == null) return;    // used cell, or no word continues this way
13    n = n.next[ch - 'a'];
14    if (n.word != null) found.add(n.word);                // a word ends here
15    b[r][c] = '#';                                        // mark visited
16    dfs(b, r + 1, c, n, found); dfs(b, r - 1, c, n, found);
17    dfs(b, r, c + 1, n, found); dfs(b, r, c - 1, n, found);
18    b[r][c] = ch;                                         // restore
19}

Live state

0 cells entered0 pruned

words

board

3×3

No condition evaluated on this step

Execution trace (dry run table)Show 10 steps

Step	Line	State	What happens
1	L2	words=3 board=3×3	All 3 words go into one trie. The board is searched once from every cell, and a branch is abandoned the moment the letters so far are not a prefix of any word.
2	L13	cell=(0, 0) letter=o path="o"	Cell (0, 0) holds 'o', and the trie has a 'o' edge here: step in. The path reads "o".
3	L13	cell=(0, 1) letter=a path="oa"	Cell (0, 1) holds 'a', and the trie has a 'a' edge here: step in. The path reads "oa".
4	L13	cell=(1, 1) letter=t path="oat"	Cell (1, 1) holds 't', and the trie has a 't' edge here: step in. The path reads "oat".
5	L13	cell=(2, 1) letter=h path="oath"	Cell (2, 1) holds 'h', and the trie has a 'h' edge here: step in. The path reads "oath".
6	L14	word="oath" found=1	The trie node ends the word "oath": it is on the board. Record it.
7	L13	cell=(1, 0) letter=e path="e"	Cell (1, 0) holds 'e', and the trie has a 'e' edge here: step in. The path reads "e".
8	L13	cell=(1, 1) letter=t path="t"	Cell (1, 1) holds 't', and the trie has a 't' edge here: step in. The path reads "t".
9	L13	cell=(1, 0) letter=e path="te"	Cell (1, 0) holds 'e', and the trie has a 'e' edge here: step in. The path reads "te".
10	L7	return=["oath"] cells entered=7 pruned=20	1 word found: "oath". The search entered 7 cells and cut 20 branches.

Practice ladder

Now try it yourself

Easy

Design Add and Search Words Data Structure
Longest Word in Dictionary

Medium

Prefix and Suffix Search
Replace Words
Word Break II

Advanced

Word Search II
Word Squares
Stream of Characters

Key takeaways

A dot makes the search branch over all children; letters keep it on one path.
Store suffix + '{' + word for every suffix to turn prefix-and-suffix queries into prefix queries.
In Word Search II, walking the trie and the board together prunes every branch that no word continues.