Prefix Count Queries
Programming Interview
Medium
4 views
Problem Description
Consider {x}. For each word, count all its prefixes. Then q prefixes are provided. For each prefix output how many words start with it.
Input Format
First line n. Next n lines words. Next line q. Next q lines prefix.
Output Format
q lines counts.
Sample Test Case
Input:
3
apple
app
bat
4
ap
app
apple
b
Constraints
Total characters
Official Solution
import sys
lines=sys.stdin.read().splitlines()
if not lines: sys.exit(0)
i=0
n=int(lines[i].strip()); i+=1
pref={}
for _ in range(n):
w=(lines[i] if i<len(lines) else '').strip(); i+=1
for j in range(1,len(w)+1):
p=w[:j]
pref[p]=pref.get(p,0)+1
q=int(lines[i].strip()) if i<len(lines) else 0
i+=1
out=[]
for _ in range(q):
p=(lines[i] if i<len(lines) else '').strip(); i+=1
out.append(str(pref.get(p,0)))
sys.stdout.write('\
'.join(out))
Solutions (0)
No solutions submitted yet. Be the first!
No comments yet. Start the discussion!