Implement Trie (Prefix Tree)
Solve this Problemwords to insert and a single query string, answer one of two questions depending on isPrefixQuery: does query match a complete inserted word exactly, or does query match at least the start of some inserted word?
Every node in the trie represents one character position; a path from the root spells out a prefix, and a node flagged as an "end" marks a spot where some inserted word actually finishes. Two words that share a prefix — like "app" and "apple" — share the same nodes along that shared path, splitting apart only where their letters first differ. Walking a query one character at a time either falls off the trie immediately (no inserted word can satisfy it) or lands on a real node — whether that counts as a match just depends on whether the query needs to be a complete word or merely a prefix.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
0 ≤ words.length ≤ 1000 - ◆
1 ≤ words[i].length ≤ 30 - ◆
0 ≤ query.length ≤ 30 - ◆
words[i] and query consist of lowercase English letters
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Linear Scan Over Word List
BruteInsert nothing anywhere — just keep the words as a plain list. For an exact-word query, walk the list checking for an identical string. For a prefix query, walk the list checking whether any word starts with it. Both checks cost O(m) per word (m = word length), so scanning all n words costs O(n · m) — correct, but every query re-examines everything from scratch.
O(n · m)O(1)1class Solution {
2 public boolean trieQuery(String[] words, String query, boolean isPrefixQuery) {
3 for (String word : words) {
4 if (isPrefixQuery) {
5 if (word.startsWith(query)) return true;
6 } else {
7 if (word.equals(query)) return true;
8 }
9 }
10 return false;
11 }
12}Optimal — Trie Traversal
OptimalBuild an actual trie: one root node, and a chain of child nodes per character for every inserted word, with an isEnd flag marking nodes where a full word ends and a count of how many inserted words pass through each node. A query then just walks the query's characters down from the root — falling off the trie (a missing child) means no word can satisfy it. Reaching the end means a word ends there (exact-match query) or at least one word passes through there (prefix query, using the count) — either way, O(m) per query after an O(N) one-time build, where N is the total characters across all inserted words.
O(N + m)O(N)1class Solution {
2 static class TrieNode {
3 TrieNode[] children = new TrieNode[26];
4 boolean isEnd = false;
5 int count = 0;
6 }
7
8 public boolean trieQuery(String[] words, String query, boolean isPrefixQuery) {
9 TrieNode root = new TrieNode();
10 for (String word : words) {
11 TrieNode node = root;
12 node.count++;
13 for (char c : word.toCharArray()) {
14 int idx = c - 'a';
15 if (node.children[idx] == null) {
16 node.children[idx] = new TrieNode();
17 }
18 node = node.children[idx];
19 node.count++;
20 }
21 node.isEnd = true;
22 }
23 TrieNode node = root;
24 for (char c : query.toCharArray()) {
25 int idx = c - 'a';
26 if (node.children[idx] == null) return false;
27 node = node.children[idx];
28 }
29 return isPrefixQuery ? node.count > 0 : node.isEnd;
30 }
31}