Given a dictionary of words and a pattern. Every character in the pattern is uniquely mapped to a character in the dictionary. Find all such words in the dictionary that match the given pattern. 
Example 1:
Input:
N = 4
dict[] = {abb,abc,xyz,xyy}
pattern  = foo
Output: abb xyy
Explanation: xyy and abb have the same
character at index 1 and 2 like the
pattern.
Your Task:
You don't need to read input or print anything. Your task is to complete the function findMatchedWords() which takes an array of strings dict[] consisting of the words in the dictionary and a string, Pattern and returns an array of strings consisting of all the words in the dict[] that match the given Pattern in lexicographical order.
Expected Time Complexity: O(N*K) (where K is the length of the pattern).
Expected Auxiliary Space: O(N).
Constraints:
1 <= N <= 10

Source: geeksforgeeks | Difficulty: EASY
Tags: String algorithms

Data structures

Starter code: #Function should return a list/array containing the required words

''' The function returns a  list of strings 
present in the dictionary which matches
the string pattern.
You are required to complete this method '''

def findSpecificPattern(Dict, pattern):
    #Code here

Solutions:
def findSpecificPattern(Dict, pattern):
	ans = []
	for i in Dict:
		dic = {}
		dic2 = {}
		if len(i) == len(pattern):
			flag = True
			for (j, k) in zip(i, pattern):
				if j not in dic and k not in dic2:
					dic[j] = k
					dic2[k] = j
				elif dic.get(j) != k or dic2.get(k) != j:
					flag = False
			if flag:
				ans.append(i)
	return ans


def findSpecificPattern(dict, pattern):
	lst = []
	for i in dict:
		if len(set(i)) == len(set(pattern)) == len(set(zip(i, pattern))) and len(i) == len(pattern):
			lst.append(i)
	return lst


def findSpecificPattern(Dict, pattern):
	d = {}
	for i in pattern:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	b = list(d.values())
	b.sort()
	a = []
	c = []
	for i in Dict:
		d2 = {}
		for j in i:
			if j in d2:
				d2[j] += 1
			else:
				d2[j] = 1
		x = list(d2.values())
		x.sort()
		a.append(x)
		c.append(i)
		d2.clear()
	d = []
	for i in range(len(a)):
		if b == a[i]:
			d.append(c[i])
	return d


def findSpecificPattern(Dict, pattern):
	a = []
	for i in Dict:
		if len(i) != len(pattern):
			continue
		d1 = {}
		d2 = {}
		for j in range(len(i)):
			if i[j] not in d1.keys() or pattern[j] not in d2.keys():
				d1[i[j]] = pattern[j]
				d2[pattern[j]] = i[j]
			elif d1[i[j]] != pattern[j] or d2[pattern[j]] != i[j]:
				break
		if len(d1) == len(d2):
			a.append(i)
	return a


def encodeString(Str):
	map = {}
	res = ''
	i = 0
	for ch in Str:
		if ch not in map:
			map[ch] = i
			i += 1
		res += str(map[ch])
	return res

def findMatchedWords(dict, pattern):
	Len = len(pattern)
	hash = encodeString(pattern)
	res = []
	for word in dict:
		if len(word) == Len and encodeString(word) == hash:
			res.append(word)
	return res

def findSpecificPattern(Dict, pattern):
	return findMatchedWords(Dict, pattern)


def findSpecificPattern(Dict, s):
	a = []
	for i in s:
		if i not in a:
			a.append(i)
	for i in range(len(a)):
		a[i] = s.count(a[i])

	def check(m):
		aa = []
		for i in m:
			if i not in aa:
				aa.append(i)
		for i in range(len(aa)):
			aa[i] = m.count(aa[i])
		return aa
	for i in Dict:
		if check(i) == a:
			print(i, end=' ')
	return []


def findSpecificPattern(Dict, pattern):
	ans = []
	flag = False
	for stri in Dict:
		flag = False
		if len(stri) == len(pattern):
			for i in range(len(pattern) - 1):
				if stri[i] != stri[i + 1] and pattern[i] != pattern[i + 1] or (stri[i] == stri[i + 1] and pattern[i] == pattern[i + 1]):
					flag = True
				else:
					flag = False
					break
			if flag == True:
				dic = {}
				pic = {}
				for i in range(len(pattern)):
					if stri[i] not in dic:
						dic[stri[i]] = 1
					else:
						dic[stri[i]] += 1
					if pattern[i] not in pic:
						pic[pattern[i]] = 1
					else:
						pic[pattern[i]] += 1
				for i in range(len(pattern)):
					if dic[stri[i]] != pic[pattern[i]]:
						flag = False
						break
			if len(stri) == 1 and len(pattern) == 1:
				ans.append(stri)
		if flag == True:
			ans.append(stri)
	return ans


def findSpecificPattern(Dict, pattern):
	a = []
	for i in Dict:
		if len(set(i)) == len(set(pattern)) and len(i) == len(pattern):
			a.append(i)
	return a


def hash_fn(word):
	k = 0
	mapper = {}
	res = ''
	for i in word:
		if i not in mapper:
			mapper[i] = k
			k += 1
		res += str(mapper[i])
	return res

def findSpecificPattern(Dict, pattern):
	ptrn_hsh = hash_fn(pattern)
	l = len(pattern)
	res = []
	for i in Dict:
		if len(i) == l and hash_fn(i) == ptrn_hsh:
			res.append(i)
	return res


def findSpecificPattern(Dict, pattern):
	matched_words = []
	for word in Dict:
		if len(word) == len(pattern):
			matched = True
			pattern_dict = {}
			for i in range(len(word)):
				if word[i] not in pattern_dict:
					if pattern[i] in pattern_dict.values():
						matched = False
						break
					pattern_dict[word[i]] = pattern[i]
				elif pattern_dict[word[i]] != pattern[i]:
					matched = False
					break
			if matched:
				matched_words.append(word)
	matched_words.sort()
	return matched_words


def findSpecificPattern(Dict, pattern):
	pattern_list = []
	for item in Dict:
		if len(item) != len(pattern):
			pattern_list.append('')
			continue
		new_pattern = pattern
		char_dict = {}
		temp_str = ''
		for i in range(len(item)):
			if item[i] in char_dict:
				temp_str = temp_str + char_dict[item[i]]
			elif new_pattern != '':
				char_dict[item[i]] = new_pattern[0]
				new_pattern = new_pattern.replace(new_pattern[0], '')
				temp_str = temp_str + char_dict[item[i]]
		pattern_list.append(temp_str)
	final_pattern = []
	for i in range(len(pattern_list)):
		if pattern_list[i] == pattern:
			final_pattern.append(Dict[i])
	return final_pattern
	return final_pattern


def findSpecificPattern(Dict, pattern):
	d = {}
	for (i, char) in enumerate(pattern):
		if char in d:
			d[char].append(i)
		else:
			d[char] = [i]
	control = sorted(d.values())
	output = []
	for word in Dict:
		temp = {}
		for (i, char) in enumerate(word):
			if char in temp:
				temp[char].append(i)
			else:
				temp[char] = [i]
		if sorted(temp.values()) == control:
			output.append(word)
	return sorted(output)


def findSpecificPattern(Dict, pattern):
	dct = {}
	arr = [0] * len(pattern)
	j = 0
	ans = []
	for i in pattern:
		if i in dct:
			dct[i] += 1
			arr[j] = dct[i]
		else:
			arr[j] = 1
			dct[i] = 1
		j += 1
	for p in Dict:
		arr2 = [0] * len(p)
		j = 0
		dct = {}
		for i in p:
			if i in dct:
				dct[i] += 1
				arr2[j] = dct[i]
			else:
				arr2[j] = 1
				dct[i] = 1
			j += 1
		if arr == arr2:
			ans.append(p)
	return ans


def findSpecificPattern(Dict, pattern):
	res = []

	def helper(pattern, elem):
		d = {}
		n = len(pattern)
		if n != len(elem):
			return
		for i in range(n):
			if pattern[i] in d and elem[i] != d[pattern[i]]:
				break
			elif pattern[i] not in d and elem[i] in d.values():
				break
			else:
				d[pattern[i]] = elem[i]
		else:
			return elem
	for x in Dict:
		if helper(pattern, x):
			res.append(helper(pattern, x))
	return res


def findSpecificPattern(Dict, pattern):
	length = len(pattern)
	hash = encodeString(pattern)
	result = []
	for word in Dict:
		if len(word) == length and encodeString(word) == hash:
			result.append(word)
	return result

def encodeString(Str):
	map = {}
	res = ''
	i = 0
	for ch in Str:
		if ch not in map:
			map[ch] = i
			i += 1
		res += str(map[ch])
	return res


def encodeString(string):
	map = {}
	res = ''
	i = 0
	for ch in string:
		if ch not in map:
			map[ch] = i
			i += 1
		res += str(map[ch])
	return res

def findSpecificPattern(Dict, pattern):
	size = len(pattern)
	hash_map = encodeString(pattern)
	output = []
	for word in Dict:
		if len(word) == size and encodeString(word) == hash_map:
			output.append(word)
	return output


def findSpecificPattern(Dict, pattern):

	def encode(word):
		m = {}
		s = ''
		counter = 0
		for c in word:
			if c not in m:
				m[c] = counter
				counter += 1
			s += str(m[c])
		return s
	pattern_hash = encode(pattern)
	result = []
	for word in Dict:
		word_hash = encode(word)
		if pattern_hash == word_hash:
			result.append(word)
	return result


def findSpecificPattern(Dict, pattern):
	d = {}
	da = []
	p = 0
	s = set(pattern)
	for i in Dict:
		if len(set(i)) == len(s):
			da.append(i)
	for i in da:
		l1 = []
		l2 = []
		c = 0
		p += 1
		for j in i:
			if l1 == []:
				l1.append(j)
				c += 1
			elif l1[-1] == j:
				l1.append(j)
				c += 1
			elif l1[-1] != j:
				l1.append(j)
				l2.append(c)
				c = 1
		if l1[-1] == i[-1]:
			l2.append(c)
			l2.insert(0, p)
			l2.insert(1, i)
		else:
			l2.append(1)
			l2.insert(0, p)
			l2.insert(1, i)
		if i not in d:
			d[i] = [l2]
		else:
			d[i].append(l2)
	k = []
	l11 = []
	l22 = []
	c1 = 0
	for i in pattern:
		if l11 == []:
			l11.append(i)
			c1 += 1
		elif l11[-1] == i:
			l11.append(i)
			c1 += 1
		elif l11[-1] != i:
			l11.append(i)
			l22.append(c1)
			c1 = 1
	if l11[-1] == pattern[-1]:
		l22.append(c1)
	else:
		l22.append(1)
	k.append(l22)
	l3 = []
	l4 = []
	for i in d:
		if d[i][0][2:] == k[-1]:
			l3.append(d[i][0] * len(d[i]))
	l3.sort()
	for i in l3:
		l4 += [i[1]] * len(d[i[1]])
	return l4


from collections import OrderedDict

def findSpecificPattern(Dict, t):
	l = []
	n = len(t)
	for j in Dict:
		d = {}
		m = len(j)
		if m != n:
			continue
		flag = 1
		for i in range(m):
			if j[i] not in d and t[i] not in d.values():
				d[j[i]] = t[i]
			elif j[i] in d and d[j[i]] != t[i]:
				flag = 0
			elif j[i] not in d and t[i] in d.values():
				flag = 0
		if flag:
			l.append(j)
	return l


from collections import OrderedDict

def findSpecificPattern(Dict, pattern):
	l = []
	for i in Dict:
		if len(i) != len(pattern) and len(set(i)) != len(set(pattern)):
			continue
		else:
			temp = i
			for j in list(zip(list(OrderedDict.fromkeys(temp)), list(OrderedDict.fromkeys(pattern)))):
				temp = temp.replace(j[0], j[1])
			if temp == pattern:
				l.append(i)
	return l


def findSpecificPattern(Dict, pattern):
	lis = []
	for i in range(len(Dict)):
		word = Dict[i]
		if len(set(word)) == len(set(pattern)) and len(word) == len(pattern):
			l = {}
			check = 1
			for i in range(len(pattern)):
				if pattern[i] in l:
					if l[pattern[i]] != word[i]:
						check = 0
						break
				else:
					l[pattern[i]] = word[i]
			if check == 1:
				lis.append(word)
	return lis


def findSpecificPattern(Dict, pattern):
	pattern_mapp = {}
	pattern_str = ''
	for (idx, char) in enumerate(pattern):
		if char not in pattern_mapp:
			pattern_mapp[char] = str(idx)
			pattern_str += str(idx)
		else:
			pattern_str += pattern_mapp[char]
	hashes = []
	for i in range(len(Dict)):
		dict_map = {}
		hash = ''
		for (idx, char) in enumerate(Dict[i]):
			if char not in dict_map:
				dict_map[char] = str(idx)
				hash += str(idx)
			else:
				hash += dict_map[char]
		if hash == pattern_str:
			hashes.append(Dict[i])
	return hashes


def Pattern(pattern):
	code = {}
	num = 1
	temp = ''
	for i in range(len(pattern)):
		if not code.get(pattern[i]):
			code[pattern[i]] = num
			num += 1
		else:
			num += 1
			code[pattern[i]] = num
	for i in pattern:
		temp += str(code[i])
	return temp

def findSpecificPattern(Dict, pattern):
	checker = Pattern(pattern)
	li = []
	for i in Dict:
		temp = Pattern(i)
		if temp == checker:
			li.append(i)
	return li


def get_hashmap(stra):
	hash_d = dict()
	for k in range(len(stra)):
		if hash_d.get(stra[k]):
			hash_d[stra[k]].append(k)
		else:
			hash_d[stra[k]] = [k]
	return set((tuple(i) for i in list(hash_d.values())))

def findSpecificPattern(Dict, pattern):
	array_pat = []
	hash_vals = get_hashmap(pattern)
	for word in Dict:
		if get_hashmap(word) == hash_vals:
			array_pat.append(word)
	array_pat.sort()
	return array_pat


from collections import Counter

def findSpecificPattern(Dict, pattern):
	ans = []
	dicpat = Counter(pattern)
	dicpatv = list(dicpat.values())
	for i in range(0, len(Dict)):
		if len(Dict[i]) == len(pattern):
			dici = Counter(Dict[i])
			dicv = list(dici.values())
			if len(dicv) == len(dicpatv):
				for j in range(0, len(dicv)):
					if dicv[j] != dicpatv[j]:
						dici = {}
						diciv = []
						continue
				ans.append(Dict[i])
				dici = {}
				diciv = []
	return ans


def findSpecificPattern(Dict, pattern):

	def getPattern(pattern):
		patt_str = ''
		val_m = {}
		count = 1
		for val in pattern:
			if val in val_m:
				patt_str += str(val_m[val])
			else:
				patt_str += str(count)
				val_m[val] = count
				count += 1
		return patt_str
	result = []
	match = getPattern(pattern)
	for val in Dict:
		p = getPattern(val)
		if p == match:
			result.append(val)
	return result


def findSpecificPattern(Dict, pattern):
	Dict.append(pattern)
	res = []
	c = 0
	p = ''
	i = 0
	k = 0
	j = 0
	for i in Dict:
		while j < len(i):
			if j == len(i) - 1:
				p += str(c)
				j += 1
				c += 1
				break
			while i[j] == i[j + 1]:
				p += str(c)
				k = 1
				j += 1
				if j == len(i) - 1:
					break
			if j == len(i) - 1:
				p += str(c)
				j += 1
				break
			p += str(c)
			j += 1
			c += 1
			k = 0
		res.append(p)
		p = ''
		j = 0
		c = 0
	p1 = res[-1]
	res1 = []
	res.pop()
	for (i, j) in enumerate(res):
		if j == p1:
			res1.append(Dict[i])
	return res1


def findSpecificPattern(Dict, pattern):
	L = []
	n = 0
	e = ''
	x = ''
	pattern = pattern + '.'
	for i in pattern:
		if i == e:
			n += 1
		else:
			x = x + str(n)
			n = 1
			e = i
	for i in Dict:
		n = 0
		e = ''
		y = ''
		i = i + '.'
		for j in i:
			if j == e:
				n += 1
			else:
				y = y + str(n)
				n = 1
				e = j
		if y == x:
			L.append(i[:-1])
	return L


def findSpecificPattern(Dict, pattern):
	result = []
	for word in Dict:
		hash = {}
		flag = True
		if len(word) != len(pattern):
			continue
		for (i, c) in enumerate(pattern):
			if c not in hash:
				hash[c] = word[i]
			elif hash[c] != word[i]:
				flag = False
		if flag:
			result.append(word)
	return result


def convert(p):
	m = {}
	r = ''
	for i in p:
		if i not in m:
			m[i] = 1
		else:
			m[i] += 1
		r = r + str(m[i])
	return r

def findSpecificPattern(Dict, pattern):
	ans = []
	pat = convert(pattern)
	for i in Dict:
		if convert(i) == pat:
			ans.append(i)
	return ans


def findSpecificPattern(Dict, pattern):
	from collections import defaultdict, OrderedDict
	(dnew, dnew2) = (defaultdict(int), defaultdict(int))
	(dnew3, dnew4) = (OrderedDict(), OrderedDict())
	(L, res) = ([], [])
	for i in Dict:
		if len(set(i)) == len(set(pattern)):
			L.append(i)
	for i in range(len(pattern)):
		dnew[pattern[i]] += 1
		dnew3[pattern[i]] = dnew[pattern[i]]
	for k in L:
		for i in range(len(k)):
			dnew2[k[i]] += 1
			dnew4[k[i]] = dnew2[k[i]]
		if list(dnew4.values()) == list(dnew3.values()):
			res.append(k)
		dnew2 = defaultdict(int)
		dnew4 = OrderedDict()
	return res


def findSpecificPattern(dictt, pattern):
	res = []

	def patterniser(strg):
		d = dict()
		lst = []
		pointer = 1
		for i in strg:
			if i not in d:
				d[i] = pointer
				pointer += 1
			lst.append(d[i])
		return lst

	def checker(pat1, pat2):
		for i in range(len(pat1)):
			if pat1[i] != pat2[i]:
				return False
		return True
	pat1 = patterniser(pattern)
	for i in dictt:
		if len(i) == len(pattern):
			pat2 = patterniser(i)
			if checker(pat1, pat2):
				res.append(i)
	return res


def findSpecificPattern(Dict, pattern):
	a = {}
	aa = []
	for i in range(len(pattern)):
		try:
			if a[pattern[i]] == 0:
				pass
		except:
			a[pattern[i]] = 0
			aa.append(pattern[i])
	pp = ''
	p = {}
	ans = []
	for i in range(len(aa)):
		p[aa[i]] = i
	for i in range(len(pattern)):
		pp += str(p[pattern[i]])
	for j in range(len(Dict)):
		a = {}
		aa = []
		for i in range(len(Dict[j])):
			try:
				if a[Dict[j][i]] == 0:
					pass
			except:
				a[Dict[j][i]] = 0
				aa.append(Dict[j][i])
		ppp = ''
		po = {}
		for i in range(len(aa)):
			po[aa[i]] = i
		for i in range(len(Dict[j])):
			ppp += str(po[Dict[j][i]])
		if pp == ppp:
			ans.append(Dict[j])
	return ans


def encodeString(Str):
	map = {}
	res = ''
	i = 0
	for ch in Str:
		if ch not in map:
			map[ch] = i
			i += 1
		res += str(map[ch])
	return res

def findSpecificPattern(Dict, pattern):
	l = []
	Len = len(pattern)
	hash = encodeString(pattern)
	for word in Dict:
		if len(word) == Len and encodeString(word) == hash:
			print(word, end=' ')
	return l


def findSpecificPattern(Dict, pattern):
	dic1 = {}
	count1 = []
	for i in pattern:
		if i not in dic1:
			dic1[i] = 1
			count1.append(dic1[i])
		else:
			dic1[i] += 1
			count1.append(dic1[i])
	dic2 = {}
	count2 = []
	output = []
	for x in Dict:
		for y in x:
			if y not in dic2:
				dic2[y] = 1
				count2.append(dic2[y])
			else:
				dic2[y] += 1
				count2.append(dic2[y])
		if count1 == count2:
			output.append(x)
		count2 = []
		dic2 = {}
	return output


def ispattern(str1, pattern, n, p):
	if n != p:
		return False
	d = {}
	for i in range(n):
		if str1[i] in d:
			val = d[str1[i]]
			if val != pattern[i]:
				return False
		elif pattern[i] not in d.values():
			d[str1[i]] = pattern[i]
		else:
			return False
	return True

def findSpecificPattern(Dict, pattern):
	ans = []
	p = len(pattern)
	for i in Dict:
		if ispattern(i, pattern, len(i), p):
			ans.append(i)
	return ans


def findSpecificPattern(Dict, pat):
	n = len(pat)
	c = 1
	l = []
	for i in range(n - 1):
		if pat[i] == pat[i + 1]:
			c += 1
		else:
			l.append(c)
			c = 1
	l.append(c)
	h = []
	for i in Dict:
		c = 1
		b = []
		n = len(i)
		for j in range(n - 1):
			if i[j] == i[j + 1]:
				c += 1
			else:
				b.append(c)
				c = 1
		b.append(c)
		if b == l:
			h.append(i)
	return h


def hashmap(Strng):
	Dic = {}
	for i in Strng:
		if i not in Dic:
			Dic[i] = 1
		else:
			Dic[i] += 1
	return Dic

def findSpecificPattern(Dict, pattern):
	kiss = []
	k = 0
	cont = 0
	ptr = {}
	for i in pattern:
		if i not in ptr:
			ptr[i] = 1
		else:
			ptr[i] += 1
	lptrn = len(ptr)
	while k < len(Dict):
		j = hashmap(Dict[k])
		ldic = len(j)
		if lptrn == ldic:
			if list(ptr.values()) == list(j.values()):
				kiss.append(Dict[k])
		k += 1
	return kiss


def search(s, n):
	dp = [1] * n
	for i in range(1, n):
		if s[i - 1] == s[i]:
			dp[i] = dp[i - 1] + 1
	return dp

def findSpecificPattern(Dict, pattern):
	p_dp = search(pattern, len(pattern))
	ans = []
	for i in Dict:
		if search(i, len(i)) == p_dp:
			ans.append(i)
	return ans


def findSpecificPattern(Dict, pattern):
	n = len(pattern)
	dp = [1] * n
	for i in range(1, n):
		if pattern[i - 1] == pattern[i]:
			dp[i] = dp[i - 1] + 1
	ans = []
	for i in Dict:
		p = [1] * len(i)
		for j in range(1, len(i)):
			if i[j - 1] == i[j]:
				p[j] = p[j - 1] + 1
		if dp == p:
			ans.append(i)
	return ans


def findSpecificPattern(Dict, pattern):
	ans = []
	for word in Dict:
		char1ToChar2 = {}
		char2ToChar1 = {}
		if len(word) == len(pattern):
			for (c1, c2) in zip(word, pattern):
				if c1 in char1ToChar2 and char1ToChar2[c1] != c2:
					break
				if c2 in char2ToChar1 and char2ToChar1[c2] != c1:
					break
				char1ToChar2[c1] = c2
				char2ToChar1[c2] = c1
			else:
				ans.append(word)
	return ans


def findSpecificPattern(Dict, pattern):
	ans = []
	for word in Dict:
		h = {}
		flag = 1
		if len(word) == len(pattern):
			for (i, j) in zip(pattern, word):
				if i not in h:
					h[i] = j
				elif h[i] != j:
					flag = 0
					break
		else:
			flag = 0
		if flag:
			ans.append(word)
	return ans


def findSpecificPattern(Dict, pattern):
	pattern_map = {}
	for i in range(len(pattern)):
		if pattern[i] not in pattern_map:
			pattern_map[pattern[i]] = 1
		else:
			pattern_map[pattern[i]] += 1
	pattern_string = ''
	values = sorted(pattern_map.values())
	for things in values:
		pattern_string += str(things)
	res = []
	for words in Dict:
		dict_map = {}
		for j in range(len(words)):
			if words[j] not in dict_map:
				dict_map[words[j]] = 1
			else:
				dict_map[words[j]] += 1
		dict_string = ''
		values2 = sorted(dict_map.values())
		for things2 in values2:
			dict_string += str(things2)
		if len(words) == len(pattern) and pattern_string == dict_string:
			res.append(words)
	return res


def findSpecificPattern(Dict, pattern):
	map_pattern = {}
	for i in range(len(pattern)):
		if pattern[i] not in map_pattern:
			map_pattern[pattern[i]] = 1
		else:
			map_pattern[pattern[i]] += 1
	pattern_string = ''
	values = sorted(map_pattern.values())
	for things in values:
		pattern_string += str(things)
	res = []
	for element in Dict:
		dict_map = {}
		for i in range(len(element)):
			if element[i] not in dict_map:
				dict_map[element[i]] = 1
			else:
				dict_map[element[i]] += 1
		dict_string = ''
		values1 = sorted(dict_map.values())
		for things2 in values1:
			dict_string += str(things2)
		if len(element) == len(pattern) and pattern_string == dict_string:
			res.append(element)
	return res


def get_pattern(s):
	d = {}
	c = 0
	unique = []
	for i in range(len(s)):
		if s[i] not in unique:
			c += 1
			unique.append(s[i])
			d[c] = [i]
		else:
			d[c].append(i)
	return d

def findSpecificPattern(Dict, pattern):
	golden = get_pattern(pattern)
	ans = []
	for i in Dict:
		temp = get_pattern(i)
		if temp == golden:
			ans.append(i)
	return ans


def findSpecificPattern(Dict, pattern):
	l = len(pattern)
	arr = [0] * l
	arr[0] = 1
	for i in range(1, l):
		if pattern[i] == pattern[i - 1]:
			arr[i] = 1 + arr[i - 1]
		else:
			arr[i] = 1
	lst = []
	for i in range(len(Dict)):
		if len(Dict[i]) == l:
			b = [0] * l
			b[0] = 1
			for j in range(1, l):
				if Dict[i][j] == Dict[i][j - 1]:
					b[j] = 1 + b[j - 1]
				else:
					b[j] = 1
			if b == arr:
				lst.append(Dict[i])
	lst.sort()
	return lst


def check_isomorphic(str1, str2):
	if len(str1) != len(str2):
		return False
	map = {}
	for i in range(len(str1)):
		if str1[i] in map:
			if map[str1[i]] != str2[i]:
				return False
		elif str2[i] not in map.values():
			map[str1[i]] = str2[i]
		else:
			return False
	return True

def findSpecificPattern(Dict, pattern):
	res = []
	N = len(Dict)
	for i in range(N):
		if check_isomorphic(Dict[i], pattern):
			res.append(Dict[i])
	return res


from collections import Counter

def findSpecificPattern(dic, pattern):
	n = len(pattern)
	mp = [0] * n
	mp[0] = 1
	for i in range(1, n):
		if pattern[i] == pattern[i - 1]:
			mp[i] = 1 + mp[i - 1]
		else:
			mp[i] = 1
	res = []
	for i in range(len(dic)):
		if len(dic[i]) == n:
			k = [0] * n
			k[0] = 1
			for j in range(1, n):
				if dic[i][j] == dic[i][j - 1]:
					k[j] = 1 + k[j - 1]
				else:
					k[j] = 1
			if k == mp:
				res.append(dic[i])
	res.sort()
	return res


def findSpecificPattern(dict, pattern):
	temp = {}
	tpat = ''
	for i in range(len(pattern)):
		if pattern[i] in temp:
			tpat += temp[pattern[i]]
		else:
			temp[pattern[i]] = str(len(temp))
			tpat += str(len(temp))
	dictp = [''] * len(dict)
	for i in range(len(dict)):
		temp = {}
		tpt = ''
		for k in range(len(dict[i])):
			if dict[i][k] in temp:
				tpt += temp[dict[i][k]]
			else:
				temp[dict[i][k]] = str(len(temp))
				tpt += str(len(temp))
		dictp[i] = tpt
	ans = []
	for i in range(len(dict)):
		if dictp[i] == tpat:
			ans.append(dict[i])
	return ans
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		n = int(input())
		arr = input().strip().split()
		string = input().strip()
		res = findSpecificPattern(arr, string)
		for i in res:
			print(i, end=' ')
		print('')


def findSpecificPattern(Dict, pattern):
	d = {}
	l = []
	for i in range(len(Dict)):
		flag = 0
		for j in range(len(Dict[i])):
			if len(Dict[i]) != len(pattern):
				flag = 1
				break
			try:
				if pattern[j] not in d:
					d[pattern[j]] = Dict[i][j]
				elif d[pattern[j]] != Dict[i][j]:
					flag = 1
					break
			except:
				flag = 1
				break
		if flag == 0:
			l.append(Dict[i])
		d = {}
	l.sort()
	return l
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		n = int(input())
		arr = input().strip().split()
		string = input().strip()
		res = findSpecificPattern(arr, string)
		for i in res:
			print(i, end=' ')
		print('')


import functools

@functools.lru_cache(maxsize=1000)
def is_isomorphic(pattern, word):
	n = len(pattern)
	d1 = {}
	for i in range(n):
		if pattern[i] not in d1:
			d1[pattern[i]] = word[i]
		elif d1[pattern[i]] != word[i]:
			return False
	t1 = ''.join((d1[v] for v in pattern))
	if t1 != word:
		return False
	d1 = {}
	for i in range(n):
		if word[i] not in d1:
			d1[word[i]] = pattern[i]
		elif d1[word[i]] != pattern[i]:
			return False
	t1 = ''.join((d1[v] for v in word))
	if t1 != pattern:
		return False
	return True

def findSpecificPattern(Dict, pattern):
	n = len(pattern)
	res = []
	for v in Dict:
		if len(v) != n:
			continue
		elif len(v) == 1:
			res.append(v)
		elif is_isomorphic(pattern, v):
			res.append(v)
	return res
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		n = int(input())
		arr = input().strip().split()
		string = input().strip()
		res = findSpecificPattern(arr, string)
		for i in res:
			print(i, end=' ')
		print('')


def findSpecificPattern(a, pat):
	l = []
	for i in a:
		m = {}
		n = {}
		if len(i) == len(pat):
			for j in range(len(pat)):
				m[i[j]] = pat[j]
				n[pat[j]] = i[j]
			if list(m.keys()) == list(n.values()) and list(n.keys()) == list(m.values()):
				l.append(i)
	return l
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		n = int(input())
		arr = input().strip().split()
		string = input().strip()
		res = findSpecificPattern(arr, string)
		for i in res:
			print(i, end=' ')
		print('')


def findSpecificPattern(d, p):
	l = []
	for i in range(len(d)):
		f = 0
		for j in range(len(p) - 1):
			if p[j] != p[j + 1] and len(d[i]) == len(p):
				if d[i][j] == d[i][j + 1]:
					f = 1
					break
			elif p[j] == p[j + 1] and len(d[i]) == len(p):
				if d[i][j] != d[i][j + 1]:
					f = 1
					break
		if len(d[i]) == len(p):
			if f == 0:
				l.append(d[i])
	return l
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		n = int(input())
		arr = input().strip().split()
		string = input().strip()
		res = findSpecificPattern(arr, string)
		for i in res:
			print(i, end=' ')
		print('')


def findSpecificPattern(Dict, pattern):
	l = []
	for i in Dict:
		if len(set(i)) == len(set(pattern)) and len(i) == len(pattern):
			l.append(i)
	return l
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		n = int(input())
		arr = input().strip().split()
		string = input().strip()
		res = findSpecificPattern(arr, string)
		for i in res:
			print(i, end=' ')
		print('')


def findSpecificPattern(Dict, pattern):
	d = {}
	h = {}
	res = ''
	x = ''
	b = []
	unique = 0
	u = 0
	j = 0
	k = 0
	for i in range(len(pattern)):
		if pattern[i] not in d.keys():
			d[pattern[i]] = 1
			unique += 1
			a = str(unique)
			res += a
		else:
			a = str(unique)
			res += a
	for j in range(len(Dict)):
		if len(Dict[j]) > len(pattern):
			continue
		for k in range(len(Dict[j])):
			if Dict[j][k] not in h.keys():
				h[Dict[j][k]] = 1
				u += 1
				a = str(u)
				x += a
			else:
				a = str(u)
				x += a
		u = 0
		h = {}
		if x == res:
			b.append(Dict[j])
		x = ''
	if len(b) >= 1:
		return b
	else:
		return -1
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		n = int(input())
		arr = input().strip().split()
		string = input().strip()
		res = findSpecificPattern(arr, string)
		for i in res:
			print(i, end=' ')
		print('')


def findSpecificPattern(Dict, pattern):
	l = []
	for i in Dict:
		if len(i) == len(pattern):
			d1 = {}
			d2 = {}
			a = 0
			for j in range(len(i)):
				if i[j] not in d1:
					if pattern[j] not in d2:
						d1[i[j]] = pattern[j]
						d2[pattern[j]] = i[j]
					else:
						a = -1
						break
				elif d1[i[j]] != pattern[j]:
					a = -1
					break
			if a == 0:
				l.append(i)
	l.sort()
	return l
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		n = int(input())
		arr = input().strip().split()
		string = input().strip()
		res = findSpecificPattern(arr, string)
		for i in res:
			print(i, end=' ')
		print('')


def findSpecificPattern(Dict, s):
	a = []
	for i in s:
		if i not in a:
			a.append(i)
	for i in range(len(a)):
		a[i] = s.count(a[i])

	def check(m):
		aa = []
		for i in m:
			if i not in aa:
				aa.append(i)
		for i in range(len(aa)):
			aa[i] = m.count(aa[i])
		return aa
	for i in Dict:
		if check(i) == a:
			print(i, end=' ')
	return []
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		n = int(input())
		arr = input().strip().split()
		string = input().strip()
		res = findSpecificPattern(arr, string)
		for i in res:
			print(i, end=' ')
		print('')


def findSpecificPattern(arr, p):
	l = len(p)
	panku = []
	for i in arr:
		k = ''
		for j in range(1, len(i)):
			if i[j] == i[j - 1]:
				k += 's'
			else:
				k += 'n'
		panku.append(k)
	req = ''
	ans = []
	for i in range(1, l):
		if p[i] == p[i - 1]:
			req += 's'
		else:
			req += 'n'
	for i in range(len(arr)):
		if panku[i] == req:
			ans.append(arr[i])
	return ans
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		n = int(input())
		arr = input().strip().split()
		string = input().strip()
		res = findSpecificPattern(arr, string)
		for i in res:
			print(i, end=' ')
		print('')


def findSpecificPattern(Dict, pattern):
	patternCount = []
	for i in pattern:
		if i not in patternCount:
			patternCount.append(i)
	for i in range(len(patternCount)):
		patternCount[i] = pattern.count(patternCount[i])

	def checkDictStrCount(string):
		dictCount = []
		for i in string:
			if i not in dictCount:
				dictCount.append(i)
		for i in range(len(dictCount)):
			dictCount[i] = string.count(dictCount[i])
		return dictCount
	for string in Dict:
		if checkDictStrCount(string) == patternCount:
			print(string, end=' ')
	return []

def findSpecificPattern(Dict, pattern):
	matchPatternStr = []
	for i in Dict:
		if len(set(i)) == len(set(pattern)) and len(i) == len(pattern):
			matchPatternStr.append(i)
	return matchPatternStr
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		n = int(input())
		arr = input().strip().split()
		string = input().strip()
		res = findSpecificPattern(arr, string)
		for i in res:
			print(i, end=' ')
		print('')


from collections import deque

def findSpecificPattern(d, p):

	def check(p, w):
		if len(p) != len(w):
			return False
		ch = [0 for i in range(128)]
		for i in range(len(p)):
			if ch[ord(p[i])] == 0:
				ch[ord(p[i])] = w[i]
			elif ch[ord(p[i])] != w[i]:
				return False
		return True
	res = deque()
	for i in range(len(d)):
		if check(p, d[i]):
			res.append(d[i])
	return res


def findSpecificPattern(Dict, pattern):
	ans = []

	def counting(Str):
		map = {}
		res = ''
		i = 0
		for ch in Str:
			if ch not in map:
				map[ch] = i
				i += 1
			res += str(map[ch])
		return res
	for word in Dict:
		pattern_res = counting(pattern)
		initial = counting(word)
		if initial == pattern_res:
			ans.append(word)
	return ans
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		n = int(input())
		arr = input().strip().split()
		string = input().strip()
		res = findSpecificPattern(arr, string)
		for i in res:
			print(i, end=' ')
		print('')


def encode(word):
	hashMap = {}
	result = ''
	i = 1
	for ch in word:
		if ch not in hashMap:
			hashMap[ch] = i
			i = i + 1
		result += str(hashMap[ch])
	return result

def findSpecificPattern(Dict, pattern):
	final = []
	for word in Dict:
		if len(word) == len(pattern) and encode(word) == encode(pattern):
			final.append(word)
	return final


def findSpecificPattern(Dict, pattern):
	list = []
	pattern = get_hash(pattern)
	for word in Dict:
		if get_hash(word) == pattern:
			list.append(word)
	return list

def get_hash(word):
	hash = str()
	dict = {}
	for (i, char) in enumerate(word):
		if not char in dict:
			dict[char] = str(i)
		hash += dict[char]
	return hash
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		n = int(input())
		arr = input().strip().split()
		string = input().strip()
		res = findSpecificPattern(arr, string)
		for i in res:
			print(i, end=' ')
		print('')


def getP(lis, pos, st):
	for i in range(len(pos)):
		if st == lis[i]:
			return pos[i]

def encodeString(string):
	lis = [-1 for x in range(len(string))]
	pos = [-1 for x in range(len(string))]
	res = ''
	p = 0
	k = 0
	for i in string:
		if i not in lis:
			lis[k] = i
			pos[k] = p
			p += 1
		else:
			lis[k] = i
			pos[k] = getP(lis, pos, i)
		k += 1
	for i in pos:
		res += str(i)
	return res

def findSpecificPattern(arr, string):
	n = len(arr)
	res = []
	tt = encodeString(string)
	l = len(string)
	for i in arr:
		if len(i) == l and tt == encodeString(i):
			res.append(i)
	return res
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		n = int(input())
		arr = input().strip().split()
		string = input().strip()
		res = findSpecificPattern(arr, string)
		for i in res:
			print(i, end=' ')
		print('')


def findSpecificPattern(Dict, pattern):
	count1 = 0
	count2 = 0
	for i in range(len(pattern) - 1):
		if pattern[i] != pattern[i + 1]:
			count1 += 1
		else:
			count2 += 1
	temp = []
	for i in Dict:
		count3 = 0
		count4 = 0
		for j in range(len(i) - 1):
			if i[j] != i[j + 1]:
				count3 += 1
			else:
				count4 += 1
		if count1 == count3 and count2 == count4:
			temp.append(i)
	return temp


from collections import defaultdict

def findSpecificPattern(Dict, pattern):
	res = []
	p = len(pattern)
	for s in Dict:
		if len(s) != p:
			continue
		d = defaultdict(str)
		flag = True
		for i in range(p):
			if s[i] not in d.keys() and pattern[i] not in d.values():
				d[s[i]] = pattern[i]
			elif d[s[i]] == pattern[i]:
				continue
			else:
				flag = False
				break
		if flag == True:
			res.append(s)
	return res


def encode_helper(word):
	count = 0
	helper_map = {}
	s = ''
	for character in word:
		if character not in helper_map:
			helper_map[character] = count
			count += 1
	for character in word:
		s = s + str(helper_map[character])
	return s

def findSpecificPattern(Dict, pattern):
	encoded_pattern = encode_helper(pattern)
	res = []
	for i in Dict:
		if encoded_pattern == encode_helper(i):
			res.append(i)
	return res


def encode(word):
	count = 0
	dit = {}
	s = ''
	for i in word:
		if i not in dit:
			dit[i] = count
			count += 1
	for i in word:
		s = s + str(dit[i])
	return s

def findSpecificPattern(Dict, pattern):
	l = []
	k = encode(pattern)
	for i in Dict:
		ans = encode(i)
		check = True
		if len(k) == len(ans):
			for j in range(len(k)):
				if k[j] != ans[j]:
					check = False
					break
			if check:
				l.append(i)
	return l


def findSpecificPattern(Dict, pattern):

	def makepattern(word):
		pr = -1
		d = {}
		res = []
		for c in word:
			if c in d:
				ind = d[c]
			else:
				d[c] = pr + 1
				pr += 1
			res.append(d[c])
		return res
	ans = []
	given_pattern = makepattern(pattern)
	for word in Dict:
		if given_pattern == makepattern(word):
			ans.append(word)
	return ans