Practice › Trie
Implement a Trie
Medium · Trie · Asked at Amazon, Google, Microsoft, Uber, Twitter
Implement a prefix tree with these operations:
insert w— add the word wsearch w— printtrueif w was inserted, elsefalsestartsWith p— printtrueif some inserted word starts with p, elsefalse
Input
First line: q. Next q lines: one operation each (lowercase words).
Output
One line for every search and startsWith.
Constraints
- 1 ≤ q ≤ 3 · 10^4
- 1 ≤ word length ≤ 30
Each node has up to 26 children and an "end of word" flag. All operations are O(length).
Example 1
Input
6 insert apple search apple search app startsWith app insert app search app
Output
true false true true
Example 2
Input
2 search a startsWith a
Output
false false
Hints
- Each node stores links to children (one per letter) and a flag "a word ends here".
- search needs the end flag on the last node; startsWith only needs the path to exist.
Approach
insert walks the word from the root, creating missing children, and marks the final node as a word end. walk(s) follows the letters and returns the reached node or null. search(w) = node exists and is a word end; startsWith(p) = node exists. All operations take O(length).
Complexity: O(length) per operation · O(total inserted length · 26) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
struct TrieNode {
int next[26];
bool end = false;
TrieNode() { memset(next, -1, sizeof next); }
};
vector<TrieNode> t(1);
int walk(const string &s) {
int cur = 0;
for (char c : s) {
cur = t[cur].next[c - 'a'];
if (cur < 0) return -1;
}
return cur;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int q;
cin >> q;
string op, w;
while (q--) {
cin >> op >> w;
if (op == "insert") {
int cur = 0;
for (char c : w) {
if (t[cur].next[c - 'a'] < 0) {
t[cur].next[c - 'a'] = t.size();
t.emplace_back();
}
cur = t[cur].next[c - 'a'];
}
t[cur].end = true;
} else {
int node = walk(w);
bool ok = op == "search" ? node >= 0 && t[node].end : node >= 0;
cout << (ok ? "true" : "false") << "\n";
}
}
return 0;
}Python solution
import sys
data = sys.stdin.read().split()
q = int(data[0])
root, END, out = {}, "$", []
def walk(s):
node = root
for c in s:
node = node.get(c)
if node is None:
return None
return node
for i in range(q):
op, w = data[1 + 2 * i], data[2 + 2 * i]
if op == "insert":
node = root
for c in w:
node = node.setdefault(c, {})
node[END] = True
elif op == "search":
node = walk(w)
out.append("true" if node is not None and END in node else "false")
else:
out.append("true" if walk(w) is not None else "false")
print("\n".join(out))Java solution
import java.util.*;
import java.io.*;
public class Main {
static class TrieNode {
TrieNode[] next = new TrieNode[26];
boolean end;
}
static TrieNode root = new TrieNode();
static TrieNode walk(String s) {
TrieNode cur = root;
for (char c : s.toCharArray()) {
cur = cur.next[c - 'a'];
if (cur == null) return null;
}
return cur;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int q = Integer.parseInt(br.readLine().trim());
StringBuilder sb = new StringBuilder();
while (q-- > 0) {
StringTokenizer st = new StringTokenizer(br.readLine());
String op = st.nextToken(), w = st.nextToken();
if (op.equals("insert")) {
TrieNode cur = root;
for (char c : w.toCharArray()) {
if (cur.next[c - 'a'] == null) cur.next[c - 'a'] = new TrieNode();
cur = cur.next[c - 'a'];
}
cur.end = true;
} else {
TrieNode node = walk(w);
boolean ok = op.equals("search") ? node != null && node.end : node != null;
sb.append(ok).append('\n');
}
}
System.out.print(sb);
}
}