Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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

  1. Checking every word for every query is O(n · q · length).
  2. 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