Practice › Trie
Count Words with a Given Prefix
Easy · Trie · Asked at Amazon, Google, Microsoft
Given a list of words and some queries, print for every query prefix how many words start with it.
Input
First line: n. Second line: n lowercase words. Third line: q. Fourth line: q prefixes.
Output
q space-separated counts.
Constraints
- 1 ≤ n, q ≤ 10^4
- 1 ≤ length of each word/prefix ≤ 20
Insert all words into a trie and store, in every node, how many words pass through it. A query walks the prefix and reads that counter.
Example 1
Input
4 apple app apply bat 3 ap b c
Output
3 1 0
Example 2
Input
2 a a 1 a
Output
2
Hints
- Checking every word for every query is O(n · q · length).
- Build a trie of the words and store in each node how many words pass through it. A query just walks down the prefix.
Approach
Each trie node has 26 child links and a counter. Inserting a word walks its letters, creating nodes as needed and incrementing the counter of every node on the way. For a prefix, walk the same way: if a letter is missing the answer is 0, otherwise it is the counter of the node where the prefix ends.
Complexity: O(total length of words + queries) time · O(total length · 26) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
struct TrieNode {
int next[26];
int pass = 0;
TrieNode() { memset(next, -1, sizeof next); }
};
vector<TrieNode> t(1);
int main() {
int n, q;
cin >> n;
for (int i = 0; i < n; i++) {
string w;
cin >> w;
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].pass++;
}
}
cin >> q;
for (int i = 0; i < q; i++) {
string p;
cin >> p;
int cur = 0;
for (char c : p) {
cur = t[cur].next[c - 'a'];
if (cur < 0) break;
}
cout << (cur < 0 ? 0 : t[cur].pass) << (i + 1 < q ? " " : "\n");
}
return 0;
}Python solution
import sys
data = sys.stdin.read().split()
n = int(data[0])
words = data[1 : 1 + n]
q = int(data[1 + n])
prefixes = data[2 + n : 2 + n + q]
root = {}
for w in words:
node = root
for c in w:
node = node.setdefault(c, {"#": 0})
node["#"] += 1
res = []
for p in prefixes:
node = root
for c in p:
node = node.get(c)
if node is None:
break
res.append(node["#"] if node else 0)
print(*res)Java solution
import java.util.*;
public class Main {
static class TrieNode {
TrieNode[] next = new TrieNode[26];
int pass;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
TrieNode root = new TrieNode();
for (int i = 0; i < n; i++) {
TrieNode cur = root;
for (char c : sc.next().toCharArray()) {
if (cur.next[c - 'a'] == null) cur.next[c - 'a'] = new TrieNode();
cur = cur.next[c - 'a'];
cur.pass++;
}
}
int q = sc.nextInt();
StringBuilder sb = new StringBuilder();
for (int i = 0; i < q; i++) {
TrieNode cur = root;
for (char c : sc.next().toCharArray()) {
cur = cur.next[c - 'a'];
if (cur == null) break;
}
sb.append(cur == null ? 0 : cur.pass).append(i + 1 < q ? " " : "");
}
System.out.println(sb);
}
}Solve Count Words with a Given Prefix online · All practice problems