Given a dictionary of words where each word follows CamelCase notation, print all words (in lexicographical order) in the dictionary that match with a given pattern consisting of uppercase characters only.
Example: GeeksForGeeks matches the pattern "GFG", because if we combine all the capital letters in GeeksForGeeks they become GFG. Also note "GeeksForGeeks" matches with the pattern "GFG" and also "GF", but not matches with "FG".
CamelCase is the practice of writing compound words or phrases such that each word or abbreviation begins with a capital letter. Common examples include PowerPoint and Wikipedia, GeeksForGeeks, CodeBlocks, etc.
Example 1:
Input:
N=3
Dictionary=["WelcomeGeek",
"WelcomeToGeeksForGeeks","GeeksForGeeks"]
Pattern="WTG"
Output:
WelcomeToGeeksForGeeks
Explanation:
Since only WelcomeToGeeksForGeeks matches 
the pattern, it is the only answer.
Example 2:
Input:
N=8
Dictionary=["Hi","Hello","HelloWorld",
"HiTech","HiGeek","HiTechWorld",
"HiTechCity","HiTechLab"]
Pattern="HA"
Output:
-1
Explanation:
Since the pattern matches none of the words
of the string,the output is -1.
Your Task:
You don't need to read input or print anything. Your Task is to complete the function CamelCase() which takes an integer N, a Vector of strings Dictionary and a string Pattern and returns the strings in the dictionary that match the pattern, if not found any return -1.
Expected Time Complexity: O(N*|S|) S=Longest string in Dictionary
Expected Auxillary Space: O(26*N)
Constraints:
1<=N<=1000
1<=|S|<=100
1<=|Pattern|<=|S|<=100
S is the longest word in Dictionary.

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: String algorithms

Data structures

Starter code: #User function Template for python3



class Solution:

    def CamelCase(self,N,Dictionary,Pattern):

        #code here

Solutions:
class Solution:

	def CamelCase(self, N, Dictionary, Pattern):
		s = ''
		l = []
		ll = {}
		ll1 = {}
		for i in range(len(Dictionary)):
			for j in Dictionary[i]:
				if j.isupper():
					s = s + j
			ll[Dictionary[i]] = s
			if Dictionary[i] not in ll1:
				ll1[Dictionary[i]] = 1
			else:
				ll1[Dictionary[i]] += 1
			s = ''
		ml = []
		for i in ll:
			j = 0
			while j < len(Pattern):
				if len(ll[i]) >= len(Pattern):
					if ll[i][j] == Pattern[j]:
						j = j + 1
					else:
						break
				else:
					break
			if j == len(Pattern):
				ml = ml + [i] * ll1[i]
		return sorted(ml)


import re

class Solution:

	def CamelCase(self, N, Dictionary, Pattern):
		new_l = []
		for i in range(len(Dictionary)):
			inside_l = Dictionary[i]
			inside_caps_l = []
			for j in range(len(inside_l)):
				if inside_l[j].isupper():
					inside_caps_l.append(inside_l[j])
			if ''.join(inside_caps_l).startswith(Pattern):
				new_l.append(Dictionary[i])
		return sorted(new_l)


class Solution:

	def CamelCase(self, N, D, Pat):
		ans = []
		for w in D:
			ext = ''.join((c for c in w if c.isupper()))
			if ext.startswith(Pat):
				ans.append(w)
		return sorted(ans)


class Solution:

	def CamelCase(self, N, Dictionary, Pattern):
		arr = []
		for item in Dictionary:
			s = ''
			for value in item:
				if value.upper() == value:
					s += value
			arr.append(s)
			s = ''
		farr = []
		for (i, v) in enumerate(arr):
			if v.__contains__(Pattern) and v.index(Pattern) == 0:
				farr.append(Dictionary[i])
		farr.sort()
		return farr


class Solution:

	def CamelCase(self, N, Dictionary, Pattern):
		output = []
		n = len(Pattern)
		for item in Dictionary:
			camel_case = ''
			for char in item:
				if char.isupper():
					camel_case += char
			if camel_case[:n] == Pattern:
				output.append(item)
		return sorted(output)


class Solution:

	def CamelCase(self, N, Dictionary, Pattern):
		ans = []
		s = ''
		for i in Dictionary:
			for j in i:
				if j.isupper():
					s += j
			if s.startswith(Pattern):
				ans.append(i)
			s = ''
		ans.sort()
		return ans


class Solution:

	def CamelCase(self, N, d, p):

		def samp(s):
			b = ''
			for i in s:
				if i.isupper():
					b += i
			return b
		e = []
		l = len(p)
		for i in d:
			if p == samp(i)[:l]:
				e += [i]
		e.sort()
		return e


class Solution:

	def CamelCase(self, N, d, p):
		l = []
		for i in d:
			s = ''
			for j in i:
				if j.isupper():
					s += j
			try:
				if s.find(p) == 0:
					l.append(i)
			except:
				continue
		l.sort()
		return l


class Solution:

	def CamelCase(self, N, Dictionary, Pattern):
		res = []
		pLen = len(Pattern)
		for wrd in Dictionary:
			ind = 0
			for c in wrd:
				if ord('A') <= ord(c) <= ord('Z'):
					if c != Pattern[ind]:
						break
					else:
						ind += 1
				if ind == pLen:
					res.append(wrd)
					break
		res.sort()
		return res


import re

class Solution:

	def CamelCase(self, N, Dictionary, Pattern):
		res = []
		pattern = re.findall('[A-Z][^A-Z]*', Pattern)
		for word in Dictionary:
			flag = True
			s = re.findall('[A-Z][^A-Z]*', word)
			ch = [w[0] for w in s]
			if len(ch) >= len(pattern) and ch[0:len(pattern)] == pattern:
				res.append(word)
		res.sort()
		return res


class Solution:

	def CamelCase(self, n, d, p):
		l = []
		for word in d:
			i = 0
			j = 0
			count = 0
			while i < len(word) and j < len(p):
				if word[i] == p[j]:
					i += 1
					j += 1
					count += 1
				elif word[i].islower():
					i += 1
				else:
					break
			if count >= len(p):
				l.append(word)
		l.sort()
		return l


class Solution:

	def CamelCase(self, N, dic, target):
		res = []
		n = len(target)
		for elm in dic:
			i = j = 0
			while i < len(elm) and j < n:
				if elm[i].isupper() and elm[i] == target[j]:
					j += 1
				elif elm[i].isupper() and elm[i] != target[j]:
					break
				i += 1
			if j == n:
				res.append(elm)
		res.sort()
		return res


class Solution:

	def CamelCase(self, N, Dictionary, Pattern):
		res = []
		pat_len = len(Pattern)
		for word in Dictionary:
			i = 0
			for c in range(len(word)):
				if 65 <= ord(word[c]) <= 90 and word[c] == Pattern[i]:
					i += 1
				elif 97 <= ord(word[c]) <= 122:
					continue
				else:
					break
				if i == pat_len:
					res.append(word)
					break
		res.sort()
		return res


class Solution:

	def isMatch(self, word, pattern):
		onlyUpper = ''
		for char in word:
			if char.isupper():
				onlyUpper += char
		return onlyUpper[:len(pattern)] == pattern

	def CamelCase(self, N, Dictionary, Pattern):
		ans = []
		for word in Dictionary:
			if self.isMatch(word, Pattern):
				ans.append(word)
		return sorted(ans)


from collections import defaultdict

class TrieNode:

	def __init__(self):
		self.links = [None] * 26
		self.endOfWord = False

class Trie:

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

	def insert(self, key):
		curr = self.root
		for ele in key:
			if not curr.links[ord(ele) - ord('A')]:
				curr.links[ord(ele) - ord('A')] = TrieNode()
			curr = curr.links[ord(ele) - ord('A')]
		curr.endOfWord = True

	def search(self, key):
		curr = self.root
		for ele in key:
			if not curr.links[ord(ele) - ord('A')]:
				return None
			curr = curr.links[ord(ele) - ord('A')]
		return curr

	def findAll(self, curr, temp, ans):
		if curr.endOfWord:
			ans += [temp]
		for i in range(26):
			if curr.links[i]:
				self.findAll(curr.links[i], temp + chr(ord('A') + i), ans)

class Solution:

	def CamelCase(self, N, Dictionary, Pattern):
		t = Trie()
		d = defaultdict(list)

		def changeString(key):
			temp = ''
			for ele in key:
				if ord(ele) < 97:
					temp += ele
			return temp
		for ele in Dictionary:
			new = changeString(ele)
			d[new] += [ele]
			t.insert(new)
		curr = t.search(Pattern)
		if curr:
			ans = []
			temp = Pattern
			t.findAll(curr, temp, ans)
			fin = []
			for ele in ans:
				fin += d[ele]
			return sorted(fin)
		return []


class Solution:

	def CamelCase(self, N, Dictionary, Pattern):
		word_with_capital_letters = list()
		for word in Dictionary:
			capital_letters = ''.join([char for char in word if ord('A') <= ord(char) <= ord('Z')])
			word_with_capital_letters.append((word, capital_letters))
		pattern_matched_strings = []
		for (word, capital_letters) in word_with_capital_letters:
			if capital_letters.startswith(Pattern):
				pattern_matched_strings.append(word)
		pattern_matched_strings.sort()
		return pattern_matched_strings


class Solution:

	def CamelCase(self, N, Dictionary, Pattern):
		x = []
		for i in Dictionary:
			s = ''
			for j in i:
				if j.isupper():
					s += j
			x.append(s)
		y = []
		for i in range(0, len(x)):
			if x[i].find(Pattern) == 0:
				y.append(Dictionary[i])
		y.sort()
		return y


class Solution:

	def CamelCase(self, N, Dictionary, Pattern):
		li = []
		for i in Dictionary:
			s = ''
			for j in i:
				if j.isupper():
					s += j
			li.append(s)
		xi = []
		for i in range(N):
			if Pattern in li[i][:len(Pattern)]:
				xi.append(Dictionary[i])
		return sorted(xi)


class Solution:

	def CamelCase(self, N, Dictionary, Pattern):
		li = []
		for i in range(len(Dictionary)):
			t = ''
			for j in range(len(Dictionary[i])):
				if Dictionary[i][j].isupper() == True:
					t += Dictionary[i][j]
			if t == Pattern or (Pattern in t and t[0] == Pattern[0]):
				li += [Dictionary[i]]
		li.sort()
		return li


import re

class Solution:

	def CamelCase(self, N, Dictionary, Pattern):
		ans = []
		for w in Dictionary:
			i = 0
			j = 0
			c = 0
			while i < len(w) and j < len(Pattern):
				if w[i] == Pattern[j]:
					i += 1
					j += 1
					c += 1
				elif (ord(w[i]) >= ord('A') and ord(w[i]) <= ord('Z')) and w[i] != Pattern[j]:
					break
				else:
					i += 1
				if c == len(Pattern):
					ans.append(w)
		ans.sort()
		return ans


class Solution:

	def CamelCase(self, N, D, P):
		b = []
		n = len(P)
		for i in D:
			t = ''
			for j in i:
				if j.isupper():
					t += j
			b.append([t, i])
		c = []
		for i in b:
			if P == i[0][:n]:
				c.append(i[1])
		c.sort()
		return c


import re

class Solution:

	def CamelCase(self, N, Dictionary, Pattern):
		d = {}
		res = []
		m = {}
		for i in Dictionary:
			t = ''.join(re.findall('[A-Z]+', i))
			d[i] = t
			if m.get(i):
				m[i] = m[i] + 1
			else:
				m[i] = 1
		for i in d:
			try:
				s = d[i].find(Pattern)
				if (Pattern in d[i] or Pattern == d[i]) and s == 0:
					if m[i] > 1:
						for z in range(m[i]):
							res = res + [i]
					else:
						res.append(i)
			except:
				print('errr')
				pass
		res.sort()
		return res


class Solution:

	def CamelCase(self, n, a, t):
		s = []
		for x in a:
			u = ''
			for y in x:
				if y.isupper():
					u += y
			if t in u[:len(t)]:
				s.append(x)
		return sorted(s)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		Dictionary = list(map(str, input().split()))
		Pattern = input()
		ob = Solution()
		ans = ob.CamelCase(N, Dictionary, Pattern)
		for i in ans:
			print(i, end=' ')
		print()


class Solution:

	def CamelCase(self, N, Dictionary, Pattern):
		from collections import defaultdict
		d = defaultdict(list)
		l = []
		res = []
		for word in Dictionary:
			temp = ''
			for i in word:
				if i.isupper():
					temp += i
			if Pattern in temp and temp.find(Pattern) == 0:
				if temp not in d:
					l.append(temp)
				d[temp].append(word)
		l.sort()
		for i in l:
			for word in d[i]:
				res.append(word)
		return res


class Solution:

	def quicksort(self, arr):
		if len(arr) == 0:
			return []
		if len(arr) == 1:
			return arr
		left = [i for i in arr[1:] if i[1] < arr[0][1]]
		right = [i for i in arr[1:] if i[1] >= arr[0][1]]
		return self.quicksort(left) + [arr[0]] + self.quicksort(right)

	def CamelCase(self, N, Dictionary, Pattern):
		l = []
		q = []
		d2 = []
		for m in Dictionary:
			s = ''
			for i in m:
				if 65 <= ord(i) <= 90:
					s += i
			l.append(s)
		for i in range(len(l)):
			d2.append([Dictionary[i], l[i]])
		d2 = self.quicksort(d2)
		for i in range(len(d2)):
			if d2[i][1].startswith(Pattern):
				q.append(d2[i][0])
		return q


class Trie:

	def __init__(self):
		self.leaf = False
		self.children = [None] * 26
		self.vector = []

class Solution:

	def traverse(self, node):
		strings = []
		if node.leaf:
			strings += node.vector
		for c in node.children:
			if c:
				strings += self.traverse(c)
		return strings

	def CamelCase(self, N, Dictionary, Pattern):
		root = Trie()
		for word in Dictionary:
			ptr = root
			for l in word:
				if l.isupper():
					index = ord(l) - 65
					if not ptr.children[index]:
						ptr.children[index] = Trie()
					ptr = ptr.children[index]
			ptr.leaf = True
			ptr.vector.append(word)
		strings = []
		for l in Pattern:
			index = ord(l) - 65
			if not root.children[index]:
				return strings
			root = root.children[index]
		return self.traverse(root)


class Solution:

	def CamelCase(self, N, Dictionary, Pattern):
		answer = []
		for i in range(N):
			Camel = ''
			for j in Dictionary[i]:
				if j.upper() == j:
					Camel += j
			if len(Camel) >= len(Pattern) and Camel[:len(Pattern)] == Pattern:
				answer.append([Camel, i])
		answer.sort()
		return [Dictionary[i[1]] for i in answer]