Geek has a list Li containing (not necessarily distinct) N words and Q queries. Each query consists of a string x. For each query, find how many strings in the List Li has the string x as its prefix. 
Example 1:
Input: 
N = 5, Q = 5
li[] = {'abracadabra', 'geeksforgeeks', 
      'abracadabra', 'geeks', 'geeksthrill'}
query[] = {'abr', 'geeks', 'geeksforgeeks', 
         'ge', 'gar'}
Output: 2 3 1 3 0
Explaination: 
Query 1: The string 'abr' is prefix of 
two 'abracadabra'. 
Query 2: The string 'geeks' is prefix of three 
strings 'geeksforgeeks', 'geeks' and 'geeksthrill'. 
Query 3: The string 'geeksforgeeks' is prefix 
of itself present in li. 
Query 4: The string 'ge' also is prefix of three 
strings 'geeksforgeeeks', 'geeks', 'geeksthrill'. 
Query 5: The string 'gar' is not a prefix of any 
string in li.
Your Task:
You do not need to read input or print anything. Your task is to complete the function prefixCount() which takes N, Q, li[] and query[] as input parameters and returns a list containing the count of prefixes for each query. 
Expected Time Complexity: O(Q*x) + O(N*L) Where Q is the number of queries, x is the longest word in the query, N = number of words inserted in Trie and L = length of longest word inserted in Trie.
Expected Auxiliary Space: O(N*List [i])
Constraints:
1 ≤ N ≤ 3 x 10^{4}
1 ≤ Q ≤ 10^{4}
1 ≤ |li[i]|, |x| ≤ 100

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Tree algorithms

Dynamic programming

Data structures

String algorithms

Starter code: # User function Template for Python3



class Solution:

    def prefixCount(self, N, Q, li, query):

        # code here

Solutions:
class Solution:

	def prefixCount(self, N, Q, li, query):
		dic = {}
		for i in range(N):
			strr = ''
			for j in li[i]:
				strr += j
				if strr not in dic:
					dic[strr] = 1
				else:
					dic[strr] += 1
		ans = []
		for i in query:
			if i in dic:
				ans.append(dic[i])
			else:
				ans.append(0)
		return ans


class Solution:

	def prefixCount(self, N, Q, li, query):
		map1 = {}
		for i in range(len(query)):
			map1[query[i]] = 0
		for item in li:
			for i in range(1, len(item) + 1):
				x = item[:i]
				if x in map1:
					map1[x] += 1
		ans = []
		for items in query:
			ans += [map1[items]]
		return ans


class TrieNode:

	def __init__(self):
		self.children = [None] * 26
		self.isEndOfWord = 0

def insert(root, key):
	cur = root
	n = len(key)
	for i in range(n):
		g = ord(key[i]) - 97
		if cur.children[g] is None:
			h = TrieNode()
			cur.children[g] = h
		cur.isEndOfWord += 1
		cur = cur.children[g]
	cur.isEndOfWord += 1

def search(root, key):
	cur = root
	n = len(key)
	c = 0
	for i in range(n):
		g = ord(key[i]) - 97
		if cur.children[g] is None:
			return 0
		cur = cur.children[g]
	return cur.isEndOfWord

class Solution:

	def prefixCount(self, N, Q, li, query):
		root = TrieNode()
		for i in li:
			insert(root, i)
		g = []
		for i in query:
			h = search(root, i)
			g.append(h)
		return g


class Node:

	def __init__(self):
		self.children = {}
		self.strings = 0
		self.end = False

class Trie:

	def __init__(self):
		self.root = Node()

	def place(self, word, pos, node):
		node.strings += 1
		if pos == len(word):
			node.end = True
			return
		if (word[pos] in node.children) == False:
			node.children[word[pos]] = Node()
		self.place(word, pos + 1, node.children[word[pos]])

	def insert(self, word: str) -> None:
		size = len(word)
		pos = 0
		node = self.root
		self.place(word, pos, node)

	def find(self, word, pos, node):
		if pos == len(word):
			return node.strings
		if (word[pos] in node.children) == False:
			return 0
		return self.find(word, pos + 1, node.children[word[pos]])

	def search(self, word: str) -> bool:
		size = len(word)
		pos = 0
		node = self.root
		return self.find(word, pos, node)

class Solution:

	def prefixCount(self, N, Q, li, query):
		Object = Trie()
		for word in li:
			Object.insert(word)
		l = []
		for q in query:
			l.append(Object.search(q))
		return l


class trie:

	def __init__(self):
		self.ch = []
		self.cnt = 0
		for i in range(26):
			self.ch.append(None)

class Solution:

	def prefixCount(self, N, Q, li, query):
		self.answer = []
		for i in range(Q):
			self.answer.append(0)
		root = trie()
		self.build(li, root)
		self.traverse(query, root)
		return self.answer

	def build(self, a, root):
		for i in a:
			temp = root
			for j in i[0]:
				if temp.ch[ord(j) - ord('a')] == None:
					temp.ch[ord(j) - ord('a')] = trie()
				temp = temp.ch[ord(j) - ord('a')]
				temp.cnt += 1

	def traverse(self, a, root):
		for i in range(len(a)):
			temp = root
			j = 0
			while j < len(a[i][0]):
				if temp.ch[ord(a[i][0][j]) - ord('a')] == None:
					break
				temp = temp.ch[ord(a[i][0][j]) - ord('a')]
				j += 1
			if j == len(a[i][0]):
				self.answer[i] = temp.cnt
			if j != len(a[i][0]):
				self.answer[i] = 0


class Solution:

	def prefixCount(self, N, Q, li, query):

		class TrieNode:

			def __init__(self):
				self.child = {}
				self.Eow = False
				self.c = 1

		def insert(word, Trie):
			for i in word:
				if i not in Trie.child:
					Trie.child[i] = TrieNode()
				else:
					Trie.child[i].c += 1
				Trie = Trie.child[i]
			Trie.Eow = True

		def dfs(Trie):
			if Trie.Eow:
				res[0] += Trie.c
			for c in Trie.child:
				dfs(Trie.child[c])

		def prefix_search(prefix, Trie):
			for ch in prefix:
				if ch in Trie.child:
					Trie = Trie.child[ch]
				else:
					return 0
			return Trie.c
		Trie = TrieNode()
		for w in li:
			insert(w[0], Trie)
		F_res = []
		for q in query:
			res = [0]
			F_res.append(prefix_search(q[0], Trie))
		return F_res


class Solution:

	def prefixCount(self, N, Q, li, query):
		new_dict = dict()
		for s in li:
			s1 = ''
			s2 = s[0]
			for i in range(0, len(s2)):
				s1 += s2[i]
				if new_dict.get(s1) == None:
					new_dict[s1] = 1
				else:
					new_dict[s1] += 1
		l = []
		for q in query:
			if new_dict.get(q[0]) == None:
				l.append(0)
			else:
				l.append(new_dict[q[0]])
		return l


class TrieNode:

	def __init__(self):
		self.links = [None] * 26
		self.cp = 0

class Trie:

	def __init__(self):
		self.root = TrieNode()

	def insert(self, key):
		curr = self.root
		for ele in key[0]:
			if not curr.links[ord(ele) - ord('a')]:
				curr.links[ord(ele) - ord('a')] = TrieNode()
			curr = curr.links[ord(ele) - ord('a')]
			curr.cp += 1

	def countPrefix(self, key):
		curr = self.root
		for ele in key[0]:
			if not curr.links[ord(ele) - ord('a')]:
				return 0
			curr = curr.links[ord(ele) - ord('a')]
		return curr.cp

class Solution:

	def prefixCount(self, N, Q, li, query):
		t = Trie()
		ans = []
		for el in li:
			t.insert(el)
		for el in query:
			ans += [t.countPrefix(el)]
		return ans


class TrieNode:

	def __init__(self) -> None:
		self.noOfStrings = 0
		self.isString = False
		self.children = [None] * 26

class Trie:

	def __init__(self):
		self.root = TrieNode()

	def insert(self, word: str) -> None:

		def self_insert(word, pos, root):
			root.noOfStrings += 1
			if pos == len(word):
				root.isString = True
				return
			if not root.children[ord(word[pos]) - ord('a')]:
				new_node = TrieNode()
				root.children[ord(word[pos]) - ord('a')] = new_node
			self_insert(word, pos + 1, root.children[ord(word[pos]) - ord('a')])
		self_insert(word, 0, self.root)

	def search(self, word: str) -> bool:

		def self_search(word, pos, root):
			if not root:
				return False
			if pos == len(word):
				return root.isString
			return self_search(word, pos + 1, root.children[ord(word[pos]) - ord('a')])
		return self_search(word, 0, self.root)

	def startsWith(self, prefix: str) -> int:

		def self_startsWith(prefix, pos, root):
			if not root:
				return 0
			if pos == len(prefix):
				return root.noOfStrings
			return self_startsWith(prefix, pos + 1, root.children[ord(prefix[pos]) - ord('a')])
		return self_startsWith(prefix, 0, self.root)

class Solution:

	def prefixCount(self, N, Q, li, query):
		trie = Trie()
		for word in li:
			trie.insert(word[0])
		ans = []
		for prefix in query:
			ans.append(trie.startsWith(prefix[0]))
		return ans


class TrieNode:

	def __init__(self) -> None:
		self.f = 0
		self.child = {}

class Solution:

	def add(self, root, s):
		for ch in s:
			if ch in root.child:
				root = root.child[ch]
			else:
				root.child[ch] = TrieNode()
				root = root.child[ch]
			root.f += 1

	def get(self, root, s):
		for ch in s:
			if ch in root.child:
				root = root.child[ch]
			else:
				return 0
		return root.f

	def prefixCount(self, n, q, arr, queries):
		root = TrieNode()
		for i in range(n):
			self.add(root, arr[i][0])
		ans = []
		for i in range(q):
			ans.append(self.get(root, queries[i][0]))
		return ans


class Solution:

	def prefixCount(self, N, Q, li, query):
		result = []
		d = {}
		for word in li:
			string = ''
			for letter in word[0]:
				string += letter
				if string in d:
					d[string] += 1
				else:
					d[string] = 1
		for prefix in query:
			if prefix[0] in d:
				result.append(d[prefix[0]])
			else:
				result.append(0)
		return result


class Solution:

	def prefixCount(self, N, Q, li, query):
		d = {}
		for i in li:
			st = ''
			for j in i[0]:
				st += j
				d[st] = d.get(st, 0) + 1
		ans = []
		for i in range(Q):
			key = query[i][0]
			if key not in d:
				ans.append(0)
			else:
				ans.append(d[key])
		return ans


class Node:

	def __init__(self):
		self.edges = {}
		self.count = 0

class Trie:

	def __init__(self):
		self.root = Node()

	def add(self, word):
		cur = self.root
		for c in word:
			if c not in cur.edges:
				cur.edges[c] = Node()
			cur = cur.edges[c]
			cur.count += 1

	def find(self, word):
		cur = self.root
		t = cur.count
		for c in word:
			if c not in cur.edges:
				return 0
			cur = cur.edges[c]
			t = cur.count
		return t

class Solution:

	def prefixCount(self, N, Q, words, queries):
		t = Trie()
		for word in words:
			t.add(word[0])
		for (i, query) in enumerate(queries):
			queries[i] = t.find(query[0])
		return queries


class Node:

	def __init__(self):
		self.c = 0
		self.end = False
		self.ptrs = [None] * 26

class Trie:

	def __init__(self):
		self.root = None

	def insert(self, word):
		if not self.root:
			self.root = Node()
		p = self.root
		for c in word:
			np = p.ptrs[ord(c) - ord('a')]
			if not np:
				p.ptrs[ord(c) - ord('a')] = Node()
			p = p.ptrs[ord(c) - ord('a')]
			p.c += 1
		p.end = True

	def search(self, word):
		if not self.root:
			return 0
		p = self.root
		for c in word:
			p = p.ptrs[ord(c) - ord('a')]
			if not p:
				return 0
		return p.c

class Solution:

	def prefixCount(self, N, Q, p, query):
		t = Trie()
		for item in p:
			t.insert(item[0])
		ans = []
		for q in query:
			ans.append(t.search(q[0]))
		return ans


from typing import List

class trie:

	def __init__(self):
		self.children = [None] * 26
		self.cnt = 0

def build(a, root):
	for i in range(len(a)):
		temp = root
		for j in range(len(a[i])):
			if temp.children[ord(a[i][j]) - ord('a')] is None:
				temp.children[ord(a[i][j]) - ord('a')] = trie()
			temp.children[ord(a[i][j]) - ord('a')].cnt += 1
			temp = temp.children[ord(a[i][j]) - ord('a')]

def find(s, root):
	for i in range(len(s)):
		if root.children[ord(s[i]) - ord('a')] == None:
			return 0
		root = root.children[ord(s[i]) - ord('a')]
	return root.cnt

class Solution:

	def prefixCount(self, N, Q, li, query):
		li = [el[0] for el in li]
		res = []
		root = trie()
		build(li, root)
		for i in range(Q):
			res.append(find(query[i][0], root))
		return res


class Solution:

	def prefixCount(self, N, Q, li, query):
		d = {}
		for i in li:
			s = ''
			for j in i[0]:
				s += j
				if s in d:
					d[s] += 1
				else:
					d[s] = 1
		m = []
		for i in query:
			if i[0] in d:
				m.append(d[i[0]])
			else:
				m.append(0)
		return m


class Solution:

	def prefixCount(self, N, Q, li, query):
		for i in range(N):
			li[i] = li[i][0]
		di = dict()
		for i in range(N):
			cu = str()
			for j in range(len(li[i])):
				cu += li[i][j]
				di[cu] = di.get(cu, 0) + 1
		ans = list()
		for i in query:
			ans.append(di.get(i[0], 0))
		return ans
		return [0] * N


class Trie:

	def __init__(self):
		self.a = {}
		self.c = {}

class Solution:

	def prefixCount(self, N, Q, li, query):
		T = Trie()
		for i in li:
			t = T
			for k in i:
				for j in k:
					if ord(j) - 97 in t.a:
						t.c[ord(j) - 97] += 1
					else:
						t.a[ord(j) - 97] = Trie()
						t.c[ord(j) - 97] = 1
					t = t.a[ord(j) - 97]
		r = []
		c = 0
		for i in query:
			t = T
			for j in i:
				f = True
				for k in j:
					if ord(k) - 97 in t.a:
						c = t.c[ord(k) - 97]
						t = t.a[ord(k) - 97]
					else:
						f = False
						break
				if f:
					r.append(c)
				else:
					r.append(0)
		return r


from collections import defaultdict

class Solution:

	def prefixCount(self, N, Q, li, query):
		d = {}
		for i in range(Q):
			d[query[i][0]] = 0
		for i in range(N):
			x = ''
			n = li[i][0]
			for j in range(len(n)):
				x += n[j]
				if x in d:
					d[x] += 1
		ans = []
		for i in query:
			ans.append(d[i[0]])
		return ans


import re

class letter:

	def __init__(self, val):
		self.value = val
		self.cntn = []
		self.count = {}

	def make_cntn(self, ltr):
		for let in self.cntn:
			if ltr == let.value:
				self.count[let] += 1
				return let
		let = letter(ltr)
		self.cntn.append(let)
		self.count[let] = 1
		return let

	def findletter(self, let):
		for ltr in self.cntn:
			if let == ltr.value:
				return (ltr, self.count[ltr])
		return (None, None)

class Solution:

	def prefixCount(self, N, Q, li, query):
		self.letters = []
		link = []
		for i in range(N):
			word = li[i][0]
			pr = None
			for j in range(len(word)):
				let = word[j]
				if pr is None:
					curr_node = self.find(j, let)
				else:
					curr_node = pr.make_cntn(let)
				pr = curr_node
		for i in range(Q):
			qry = query[i][0]
			ln = len(qry)
			st = qry[0]
			x = None
			idx = 1
			for x in self.letters[0]:
				if x.value == st:
					break
			count = 0
			while x is not None and idx < ln:
				nt = qry[idx]
				(nt, ncount) = x.findletter(nt)
				if nt is None:
					count = 0
					break
				count = ncount
				x = nt
				idx += 1
			query[i] = count
		return query

	def find(self, level, ltr):
		try:
			level_content = self.letters[level]
		except:
			self.letters.append(set())
			new = letter(ltr)
			self.letters[level].add(new)
			return new
		for node in level_content:
			if node.value == ltr:
				return node
		new = letter(ltr)
		level_content.add(new)
		return new


class Trienode:

	def __init__(self):
		self.child = [None] * 26
		self.count = 0

class Trie:

	def __init__(self):
		self.root = Trienode()

	def insert(self, word):
		cur = self.root
		word = word[0]
		n = len(word)
		for c in word:
			temp = ord(c) - 97
			if cur.child[temp] is None:
				cur.child[temp] = Trienode()
			cur = cur.child[temp]
			cur.count += 1

	def search(self, pre):
		cur = self.root
		pre = pre[0]
		for i in pre:
			temp = ord(i) - 97
			if cur.child[temp] == None:
				return 0
			cur = cur.child[temp]
		return cur.count

class Solution:

	def prefixCount(self, N, Q, li, query):
		out = []
		t = Trie()
		for i in li:
			t.insert(i)
		for i in query:
			out.append(t.search(i))
		return out


class TrieNode:

	def __init__(self):
		self.children = [None for i in range(26)]
		self.count = 0

class Trie:

	def __init__(self):
		self.root = self.getNode()

	def getNode(self):
		return TrieNode()

	def _charToIndex(self, ch):
		return ord(ch) - ord('a')

	def insert(self, key):
		pCrawl = self.root
		length = len(key)
		for level in range(length):
			index = self._charToIndex(key[level])
			if not pCrawl.children[index]:
				pCrawl.children[index] = self.getNode()
			pCrawl.children[index].count += 1
			pCrawl = pCrawl.children[index]

	def search(self, key):
		pCrawl = self.root
		length = len(key)
		for level in range(length):
			index = self._charToIndex(key[level])
			if not pCrawl.children[index]:
				return 0
			pCrawl = pCrawl.children[index]
		return pCrawl.count

class Solution:

	def prefixCount(self, N, Q, li, query):
		a = Trie()
		li_1 = [i[0] for i in li]
		query_1 = [i[0] for i in query]
		for i in li_1:
			a.insert(i)
		l = []
		for i in query_1:
			l.append(a.search(i))
		return l


def charToIndex(ch):
	return ord('a') - ord(ch)

class Node:

	def __init__(self):
		self.children = {}
		self.cnt = {}
		self.endWord = False

class Trie:

	def __init__(self):
		self.root = Node()

	def insert(self, word):
		ptr = self.root
		for i in word:
			if i not in ptr.children:
				ptr.children[i] = Node()
				ptr.cnt[i] = 1
			else:
				ptr.cnt[i] += 1
			ptr = ptr.children[i]
		ptr.endWord = True

	def search(self, word):
		ptr = self.root
		for i in word:
			ind = charToIndex(i)
			if not ptr.children[ind]:
				return False
			ptr = ptr.children[ind]
		return ptr.endWord

	def prefix(self, word):
		ptr = self.root
		c = 0
		for i in word:
			if i not in ptr.children:
				return 0
			c = ptr.cnt[i]
			ptr = ptr.children[i]
		return c

class Solution:

	def prefixCount(self, N, Q, li, query):
		l = []
		trie = Trie()
		for i in li:
			trie.insert(i[0])
		for i in query:
			l.append(trie.prefix(i[0]))
		return l


class Solution:

	def prefixCount(self, N, Q, li, query):
		prefix_map = {}
		for string in li:
			temp = ''
			for i in string[0]:
				temp += i
				prefix_map[temp] = prefix_map.get(temp, 0) + 1
		return [prefix_map.get(string[0], 0) for string in query]


class TrieNode:

	def __init__(self, char):
		self.char = char
		self.num = 0
		self.is_end = False
		self.children = {}

class Trie(object):

	def __init__(self):
		self.root = TrieNode('')

	def insert(self, word):
		node = self.root
		node.num += 1
		for char in word:
			if char in node.children:
				node = node.children[char]
			else:
				new_node = TrieNode(char)
				node.children[char] = new_node
				node = new_node
			node.num += 1
		node.is_end = True

	def count(self, prefix):
		n = self.root
		while prefix != '':
			c = prefix[0]
			if c in n.children:
				n = n.children[c]
				prefix = prefix[1:]
			else:
				return 0
		return n.num

class Solution:

	def prefixCount(self, N, Q, li, query):
		query = [q[0] for q in query]
		li = [l[0] for l in li]
		tr = Trie()
		for l in li:
			tr.insert(l)
		return [tr.count(q) for q in query]


class Solution:

	def prefixCount(self, N, Q, li, query):
		res = {}
		reslst = [0] * Q
		temp = 0
		for i in li:
			for j in range(len(i[0]) + 1):
				if i[0][0:j] not in res.keys():
					res[i[0][0:j]] = 1
				else:
					res[i[0][0:j]] = res[i[0][0:j]] + 1
		for i in range(Q):
			if query[i][0] in res.keys():
				reslst[i] = res[query[i][0]]
		return reslst


class Solution:

	def prefixCount(self, N, Q, li, query):
		d = {}
		for i in li:
			s = ''
			for char in i[0]:
				s += char
				if s in d:
					d[s] += 1
				else:
					d[s] = 1
		res = []
		for pre in query:
			if pre[0] in d:
				res.append(d[pre[0]])
			else:
				res.append(0)
		return res


class Solution:

	def prefixCount(self, N, Q, li, query):

		class node:

			def __init__(self):
				self.count = 0
				self.next = {}
		trie = node()
		for word in li:
			t = trie
			word = word[0]
			for c in word:
				if c not in t.next:
					a = node()
					t.next[c] = a
				t = t.next[c]
				t.count += 1
		op = []
		for word in query:
			t = trie
			flag = 0
			word = word[0]
			for c in word:
				if c not in t.next:
					flag = 1
					break
				t = t.next[c]
			if flag == 1:
				op.append(0)
			else:
				op.append(t.count)
		return op


class Solution:

	def prefixCount(self, N, Q, li, query):
		d = {}
		for i in li:
			x = ''
			for j in i[0]:
				x += j
				if x in d:
					d[x] += 1
				else:
					d[x] = 1
		ans = []
		for i in query:
			if i[0] in d:
				ans.append(d[i[0]])
			else:
				ans.append(0)
		return ans


class Trie:

	def __init__(self):
		self.child = {}
		self.pc = 0

def insert(root, word):
	curr = root
	for c in word:
		if c not in curr.child:
			curr.child[c] = Trie()
			curr.child[c].pc += 1
			curr = curr.child[c]
		else:
			curr = curr.child[c]
			curr.pc += 1

def prefixcnt(root, word):
	curr = root
	for c in word:
		if c not in curr.child:
			return 0
		curr = curr.child[c]
	return curr.pc

class Solution:

	def prefixCount(self, N, Q, li, query):
		root = Trie()
		for item in li:
			word = item[0]
			insert(root, word)
		ans = []
		for item in query:
			word = item[0]
			cnt = prefixcnt(root, word)
			ans.append(cnt)
		return ans


class Solution:

	def prefixCount(self, N, Q, li, query):
		count = dict()
		for word in li:
			for i in range(1, len(word[0]) + 1):
				count[word[0][:i]] = count.get(word[0][:i], 0) + 1
		return [count.get(q[0], 0) for q in query]


class Node:

	def __init__(self, val=None):
		self.val = val
		self.child = [None] * 26
		self.co = 0
		self.isend = False

class Trie:

	def __init__(self):
		self.ans = Node()

	def insert(self, word: str) -> None:
		t = self.ans
		for i in word:
			if t.child[ord(i) - 97] != None:
				t.co += 1
				t = t.child[ord(i) - 97]
			else:
				t.co += 1
				t.child[ord(i) - 97] = Node(i)
				t = t.child[ord(i) - 97]
		t.co += 1
		t.isend = True

	def startsWith(self, word: str) -> bool:
		t = self.ans
		n = len(word)
		c = 0
		for i in word:
			if t.child[ord(i) - 97] != None:
				t = t.child[ord(i) - 97]
				c += 1
			else:
				break
		if c == n:
			return t.co
		return 0

class Solution:

	def prefixCount(self, N, Q, li, query):
		ans = []
		obj = Trie()
		for word in li:
			obj.insert(word[0])
		for qur in query:
			ans.append(obj.startsWith(qur[0]))
		return ans


class Solution:

	def prefixCount(self, N, Q, li, query):
		mp = {}
		for i in range(N):
			s = ''
			for j in li[i][0]:
				s += j
				mp[s] = mp.get(s, 0) + 1
		l = [0 for _ in range(Q)]
		for i in range(Q):
			l[i] = mp.get(query[i][0], 0)
		return l


class TrieNode:

	def __init__(self):
		self.children = [None] * 26
		self.isEndOfWord = 0
		self.down = 0

class Trie:

	def __init__(self):
		self.root = self.getNode()

	def getNode(self):
		return TrieNode()

	def _charToIndex(self, ch):
		return ord(ch) - ord('a')

	def insert(self, key):
		pCrawl = self.root
		length = len(key)
		for level in range(length):
			index = self._charToIndex(key[level])
			if not pCrawl.children[index]:
				pCrawl.children[index] = self.getNode()
			pCrawl = pCrawl.children[index]
			pCrawl.down += 1

	def search(self, key):
		pCrawl = self.root
		length = len(key)
		for level in range(length):
			index = self._charToIndex(key[level])
			if not pCrawl.children[index]:
				return 0
			pCrawl = pCrawl.children[index]
		return pCrawl.down

class Solution:

	def prefixCount(self, N, Q, li, query):
		t = Trie()
		arr = []
		for l in li:
			arr.append(l[0])
		arr.sort()
		for a in arr:
			t.insert(a)
		ans = []
		for q in query:
			ans.append(t.search(q[0]))
		return ans


class Trie:

	def __init__(self):
		self.child = [None] * 26
		self.count = 0

def add_word(s, w):
	(i, temp) = (0, s)
	while i < len(w):
		if not temp.child[ord(w[i]) - ord('a')]:
			temp.child[ord(w[i]) - ord('a')] = Trie()
		temp = temp.child[ord(w[i]) - ord('a')]
		temp.count += 1
		i += 1

def search_prefix(s, w):
	count = 0
	(i, temp) = (0, s)
	while i < len(w):
		if not temp.child[ord(w[i]) - ord('a')]:
			return 0
		temp = temp.child[ord(w[i]) - ord('a')]
		i += 1
	return temp.count

class Solution:

	def prefixCount(self, N, Q, li, query):
		start = Trie()
		ans = []
		for w in li:
			add_word(start, w[0])
		for w in query:
			ans.append(search_prefix(start, w[0]))
		return ans


class Solution:

	def prefixCount(self, N, Q, li, query):
		d = {}
		for s in li:
			s = s[0]
			for i in range(len(s)):
				x = s[:i + 1]
				d[x] = d.get(x, 0) + 1
		res = []
		for i in query:
			res.append(d.get(i[0], 0))
		return res


class Node:

	def __init__(self):
		self.arr = [None] * 26
		self.freq = 0

class Trie:

	def __init__(self):
		self.root = self.getNode()

	def getNode(self):
		return Node()

	def insert(self, s):
		_in = 0
		cur = self.root
		for i in range(len(s)):
			_in = ord(s[i]) - ord('a')
			if not cur.arr[_in]:
				cur.arr[_in] = self.getNode()
			cur.arr[_in].freq += 1
			cur = cur.arr[_in]

	def find(self, s):
		_in = 0
		cur = self.root
		num = len(s)
		count = 0
		for i in range(num):
			_in = ord(s[i]) - ord('a')
			if cur.arr[_in] == None:
				return 0
			cur = cur.arr[_in]
			count += 1
			if count == num:
				return cur.freq
		return 0

class Solution:

	def prefixCount(self, N, Q, li, query):
		root = Trie()
		res = []
		for i in range(N):
			root.insert(li[i][0])
		for i in range(Q):
			t = root.find(query[i][0])
			res.append(t)
		return res


class TrieNode:

	def __init__(self):
		self.hashmap = {}
		self.count = 1

class Solution:

	def prefixCount(self, N, Q, li, query):
		li = [i[0] for i in li]
		query = [i[0] for i in query]
		self.root = TrieNode()
		self.insert(N, li)
		res = []
		res = self.search(Q, query, res)
		return res

	def insert(self, n, words):
		for word in words:
			self.insertHelper(word)

	def search(self, n, pre, res):
		visited = {}
		for prefix in pre:
			if prefix not in visited:
				ans = self.searchHelper(prefix)
				visited[prefix] = ans
			else:
				ans = visited[prefix]
			res.append(ans)
		return res

	def insertHelper(self, word):
		cur = self.root
		for char in word:
			if char in cur.hashmap:
				cur = cur.hashmap[char]
				cur.count += 1
			else:
				cur.hashmap[char] = TrieNode()
				cur = cur.hashmap[char]

	def searchHelper(self, prefix):
		cur = self.root
		total = 0
		for char in prefix:
			if char in cur.hashmap:
				cur = cur.hashmap[char]
				total = cur.count
			else:
				total = 0
				break
		return total


from collections import defaultdict

class Solution:

	def prefixCount(self, N, Q, li, query):
		ans = []
		dt = defaultdict(bool)
		di = defaultdict(int)
		for i in range(Q):
			dt[query[i][0]] = True
		for i in range(N):
			for j in range(1, len(li[i][0]) + 1):
				if dt[li[i][0][:j]]:
					di[li[i][0][:j]] += 1
		for i in range(Q):
			ans.append(di[query[i][0]])
		return ans


class Solution:

	def prefixCount(self, N, Q, li, query):
		trie = Trie()
		for word in li:
			trie.addWord(word[0])
		output = []
		for word in query:
			output.append(trie.getPrefixCount(word[0]))
		return output

class Trie:

	def __init__(self):
		self.charCount = '#'
		self.root = {self.charCount: 0}

	def addWord(self, word):
		current = self.root
		for char in word:
			if char not in current:
				current[char] = {self.charCount: 0}
			current = current[char]
			current[self.charCount] += 1

	def getPrefixCount(self, word):
		current = self.root
		for char in word:
			if char not in current:
				return 0
			current = current[char]
		return current[self.charCount]


class Trie:

	def __init__(self):
		self.arr = [None for i in range(26)]
		self.count = 0
		self.flag = False

class Solution:

	def prefixCount(self, N, Q, li, query):
		T = Trie()
		for x in li:
			word = x[0]
			self.insert(word, T)
		ansarr = [0 for i in range(Q)]
		for i in range(Q):
			prefix = query[i][0]
			ans = self.pref(prefix, T)
			ansarr[i] = ans
		return ansarr

	def pref(self, prefix, trie):
		root = trie
		for x in prefix:
			idx = ord(x) - ord('a')
			if root.arr[idx]:
				root = root.arr[idx]
			else:
				return 0
		return root.count

	def insert(self, word, trie):
		root = trie
		for x in word:
			char = x
			idx = ord(char) - ord('a')
			root.count += 1
			if root.arr[idx]:
				root = root.arr[idx]
			else:
				root.arr[idx] = Trie()
				root = root.arr[idx]
		root.count += 1
		root.flag = True


class TrieNode:

	def __init__(self, char):
		self.char = char
		self.is_end = False
		self.counter = 0
		self.children = {}

class Trie(object):

	def __init__(self):
		self.root = TrieNode('')

	def insert(self, word):
		node = self.root
		for char in word:
			if char in node.children:
				node = node.children[char]
				node.counter += 1
			else:
				new_node = TrieNode(char)
				node.children[char] = new_node
				node = new_node
				node.counter += 1
		node.is_end = True

	def search(self, x):
		node = self.root
		res = 0
		for char in x:
			if char not in node.children:
				res = 0
				break
			elif char in node.children:
				node = node.children[char]
				res = node.counter
		return res

class Solution:

	def prefixCount(self, N, Q, li, query):
		trie = Trie()
		for word in li:
			trie.insert(word[0])
		output = []
		for q in query:
			a = trie.search(q[0])
			output.append(a)
		return output


class TrieNode:

	def __init__(self):
		self.chars = [None] * 26
		self.c = 0
		self.isword = False

class Trie:

	def __init__(self):
		self.root = TrieNode()

	def insert(self, s):
		curr = self.root
		for ch in s:
			o = ord(ch) - ord('a')
			if curr.chars[o] is None:
				curr.chars[o] = TrieNode()
			curr = curr.chars[o]
			curr.c += 1
		curr.isword = True

	def search(self, s):
		curr = self.root
		for ch in s:
			o = ord(ch) - ord('a')
			if curr.chars[o] is None:
				return 0
			curr = curr.chars[o]
		return curr.c

class Solution:

	def prefixCount(self, N, Q, li, query):
		trie = Trie()
		for S in li:
			trie.insert(S[0])
		ans = []
		for q in query:
			ans.append(trie.search(q[0]))
		return ans


class TrieNode:

	def __init__(self, char):
		self.char = char
		self.is_end = False
		self.counter = 0
		self.children = {}

class Trie(object):

	def __init__(self):
		self.root = TrieNode('')

	def insert(self, word):
		node = self.root
		for char in word:
			if char in node.children:
				node = node.children[char]
			else:
				new_node = TrieNode(char)
				node.children[char] = new_node
				node = new_node
			node.counter += 1
		node.is_end = True

	def query(self, x):
		self.output = []
		node = self.root
		for char in x:
			if char in node.children:
				node = node.children[char]
			else:
				return 0
		return node.counter

class Solution:

	def prefixCount(self, N, Q, li, query):
		t = Trie()
		res = []
		for w in li:
			w = w[0]
			t.insert(w)
		for q in query:
			q = q[0]
			re = t.query(q)
			res.append(re)
		return res


class Trie:

	def __init__(self, val):
		self.val = val
		self.dic = {}
		self.count = 0
		self.isEnd = False

class Solution:

	def insert(self, curr, nums):
		for (index, ch) in enumerate(nums):
			if ch not in curr.dic:
				new_node = Trie(ch)
				curr.dic[ch] = new_node
			curr = curr.dic[ch]
			curr.count += 1
		curr.isEnd = True

	def search(self, curr, nums, temp=0):
		for ch in nums:
			if ch not in curr.dic:
				return 0
			curr = curr.dic[ch]
		return curr.count

	def prefixCount(self, N, Q, li, query):
		ans = []
		root = Trie('')
		for i in li:
			self.insert(root, i[0])
		for i in query:
			ans.append(self.search(root, i[0]))
		return ans


class Node:

	def __init__(self):
		self.links = [False] * 26
		self.pre_cnt = 0

	def containsKey(self, char):
		return self.links[ord(char) - ord('a')]

	def put(self, char, node):
		self.links[ord(char) - ord('a')] = node

	def get(self, char):
		return self.links[ord(char) - ord('a')]

class Trie:

	def __init__(self):
		self.root = Node()

	def insert(self, word):
		node = self.root
		for char in word:
			if not node.containsKey(char):
				node.put(char, Node())
			node = node.get(char)
			node.pre_cnt += 1

	def search(self, word):
		node = self.root
		for char in word:
			if not node.containsKey(char):
				return 0
			node = node.get(char)
		return node.pre_cnt

class Solution:

	def prefixCount(self, N, Q, li, query):
		li = [i[0] for i in li]
		query = [i[0] for i in query]
		trie = Trie()
		for word in li:
			trie.insert(word)
		ans = []
		for word in query:
			ans.append(trie.search(word))
		return ans


from collections import defaultdict

class Solution:

	def prefixCount(self, N, Q, li, query):
		d = defaultdict(int)
		for word in li:
			for i in range(len(word[0])):
				d[word[0][:i + 1]] += 1
		ans = []
		for q in query:
			ans.append(d[q[0]])
		return ans


class Solution:

	def prefixCount(self, N, Q, li, query):
		x = {}
		for i in li:
			a = ''
			for j in i[0]:
				a += j
				if a in x:
					x[a] += 1
				else:
					x[a] = 1
		b = []
		for i in query:
			if i[0] in x:
				b.append(x[i[0]])
			else:
				b.append(0)
		return b


class Solution:

	def prefixCount(self, n, q, l1, query):
		mp = {}
		for i in range(q):
			mp[query[i][0]] = 0
		res = [0 for i in range(q)]
		for i in range(n):
			s = ''
			tmp = l1[i][0]
			c = 0
			for j in range(len(tmp)):
				s += tmp[j]
				if s in mp:
					mp[s] += 1
					c += 1
		for i in range(q):
			res[i] = mp[query[i][0]]
		return res


class Solution:

	def prefixCount(self, N, Q, li, query):
		trie = {}
		end = '*'

		def recur(curTrie):
			if not curTrie:
				return 0
			count = 0
			if end in curTrie:
				count += curTrie[end]
			for char in curTrie:
				if char == end:
					continue
				count += recur(curTrie[char])
			return count
		for word in li:
			cur = trie
			for char in word[0]:
				if char not in cur:
					cur[char] = {}
				cur = cur[char]
			if end not in cur:
				cur[end] = 0
			cur[end] += 1
		result = []
		cache = {}
		for word in query:
			if word[0] in cache:
				result.append(cache[word[0]])
				continue
			cur = trie
			for char in word[0]:
				if char not in cur:
					cur = None
					break
				cur = cur[char]
			if not cur:
				word[0] = 0
				result.append(0)
				continue
			cache[word[0]] = recur(cur)
			result.append(cache[word[0]])
		return result