Given an array of words, find all shortest unique prefixes to represent each word in the given array. Assume that no word is prefix of another.
Example 1:
Input: 
N = 4
arr[] = {"zebra", "dog", "duck", "dove"}
Output: z dog du dov
Explanation: 
z => zebra 
dog => dog 
duck => du 
dove => dov 
Example 2:
Input: 
N = 3
arr[] =  {"geeksgeeks", "geeksquiz",
                       "geeksforgeeks"};
Output: geeksg geeksq geeksf
Explanation: 
geeksgeeks => geeksg 
geeksquiz => geeksq 
geeksforgeeks => geeksf
Your task:
You don't have to read input or print anything. Your task is to complete the function findPrefixes() which takes the array of strings and it's size N as input and returns a list of shortest unique prefix for each word 
 
Expected Time Complexity: O(N*length of each word)
Expected Auxiliary Space: O(N*length of each word)
 
Constraints:
1 ≤ N, Length of each word ≤ 1000

Source: geeksforgeeks | Difficulty: MEDIUM_HARD
Tags: String algorithms

Data structures

Starter code: #User function Template for python3

class Solution:
    def findPrefixes(self, arr, N):
        # code here 

Solutions:
class TrieNode:

	def __init__(self):
		self.children = {}
		self.freq = 0

class Solution:

	def insert(self, root, st):
		for i in range(len(st)):
			c = st[i]
			if c not in root.children:
				root.children[c] = TrieNode()
			root = root.children[c]
			root.freq += 1

	def get_prefix(self, root, st):
		pref = ''
		for i in range(len(st)):
			c = st[i]
			if root.freq == 1:
				break
			pref += c
			root = root.children[c]
		return pref

	def findPrefixes(self, arr, n):
		root = TrieNode()
		for word in arr:
			self.insert(root, word)
		ans = []
		for word in arr:
			ans.append(self.get_prefix(root, word))
		return ans


class Solution:

	def findPrefixes(self, arr, N):
		result = []
		for i in range(N):
			target = arr[i]
			s = target[0]
			k = 1
			j = 0
			while j < N:
				if arr[j][:k] == s and j != i:
					k += 1
					s = target[:k]
				else:
					j += 1
			result.append(s)
		return result


class TrieNode:

	def __init__(self, char):
		self.char = char
		self.children = {}

class Solution:

	def insert(node, word):
		head = node
		for c in word:
			if c not in head.children.keys():
				new_node = TrieNode(c)
				head.children[c] = new_node
				head = new_node
			else:
				head = head.children[c]
		head.isEnd = True

	def query(node, word):
		head = node
		(c, prefix) = (0, '')
		sen = ''
		while c < len(word):
			tmp = False
			sen += word[c]
			if len(head.children) > 1:
				tmp = True
				prefix = sen
			head = head.children[word[c]]
			c += 1
		if prefix == '':
			prefix = sen
		return prefix

	def findPrefixes(self, arr, N):
		root = TrieNode('-1')
		out = []
		for string in arr:
			Solution.insert(root, string)
		for string in arr:
			out.append(Solution.query(root, string))
		return out


class Solution:

	def findPrefixes(self, arr, N):

		class TrieNode:

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

		class Trie:

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

			def insert(self, key):
				node = self.root
				x = ord('a')
				for ch in key:
					index = ord(ch) - x
					if node.children[index] is None:
						node.children[index] = TrieNode()
					node = node.children[index]
					node.count += 1

			def unique_prefix(self, s):
				res = ''
				x = ord('a')
				temp = self.root
				for ch in s:
					res += ch
					temp = temp.children[ord(ch) - x]
					if temp.count == 1:
						return res
		ans = Trie()
		for word in arr:
			ans.insert(word)
		return [ans.unique_prefix(i) for i in arr]


class TrieNode:

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

	def insert(root, word):
		for c in word:
			if c not in root.children:
				root.children[c] = TrieNode()
			root = root.children[c]
			root.count += 1
		root.isEnd = True

	def findPrefix(root, word):
		ans = ''
		for c in word:
			ans += c
			root = root.children[c]
			if root.count == 1:
				return ans
		raise NotImplementedError

class Solution:

	def findPrefixes(self, arr, N):
		ans = []
		root = TrieNode()
		for word in arr:
			TrieNode.insert(root, word)
		for word in arr:
			ans.append(TrieNode.findPrefix(root, word))
		return ans


class TrieNode:

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

class Trie:

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

	def insert(self, word):
		cur = self.root
		for c in word:
			if c not in cur.children:
				cur.children[c] = TrieNode()
			cur = cur.children[c]
			cur.count += 1

	def search(self, word):
		cur = self.root
		prefix = []
		for c in word:
			if cur.count == 1:
				return ''.join(prefix)
			prefix.append(c)
			cur = cur.children[c]
		return word

class Solution:

	def findPrefixes(self, s, n):
		t = Trie()
		for w in s:
			t.insert(w)
		ans = []
		for w in s:
			ans.append(t.search(w))
		return ans


class TrieNode:

	def __init__(self):
		self.child = dict()
		self.count = 0
		self.endOfWord = False

class Trie:

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

	def insert(self, word):
		ptr = self.root
		for c in word:
			ptr.count += 1
			ptr.child[c] = ptr.child.get(c, TrieNode())
			ptr = ptr.child[c]
		ptr.endOfWord = True

	def getUniquePrefix(self, word):
		ptr = self.root
		ans = ''
		for c in word:
			ans += c
			ptr = ptr.child[c]
			if ptr.count <= 1:
				break
		return ans

class Solution:

	def findPrefixes(self, arr, N):
		trie = Trie()
		for word in arr:
			trie.insert(word)
		unique = []
		for word in arr:
			unique.append(trie.getUniquePrefix(word))
		return unique


class Node:

	def __init__(self, ch):
		self.childrens = [None] * 26
		self.freq = 1
		self.is_terminal = False

	def __str__(self) -> str:
		return self.data

class Trie:

	def __init__(self):
		self.root = Node('\x00')

	def insert(self, root, word):
		for ch in word:
			idx = ord(ch) - ord('a')
			if root.childrens[idx] is None:
				root.childrens[idx] = Node(ch)
			else:
				root.childrens[idx].freq += 1
			root = root.childrens[idx]
		root.is_terminal = True

class Solution:

	def get_prefix(self, root, word):
		prefix = ''
		for ch in word:
			prefix += ch
			idx = ord(ch) - ord('a')
			if root.childrens[idx].freq == 1:
				return prefix
			root = root.childrens[idx]
		return prefix

	def findPrefixes(self, arr, N):
		t = Trie()
		for word in arr:
			t.insert(t.root, word)
		ans = []
		for word in arr:
			ans.append(self.get_prefix(t.root, word))
		return ans


class TrieNode:

	def __init__(self):
		self.char_dict = {}
		self.freq = 0

class Solution:

	def Construct_Trie(self, arr):
		root = TrieNode()
		for word in arr:
			temp_root = root
			for char in word:
				if char in temp_root.char_dict:
					temp_root = temp_root.char_dict[char]
					temp_root.freq += 1
				else:
					temp_root.char_dict[char] = TrieNode()
					temp_root.char_dict[char].freq = 1
					temp_root = temp_root.char_dict[char]
		return root

	def Get_Smallest_Prefix_Arr(self, arr, root):
		ans = []
		for word in arr:
			(temp_root, smallest_prefix) = (root, '')
			for char in word:
				smallest_prefix += char
				if temp_root.char_dict[char].freq == 1:
					ans.append(smallest_prefix)
					break
				temp_root = temp_root.char_dict[char]
		return ans

	def findPrefixes(self, arr, N):
		root = self.Construct_Trie(arr)
		return self.Get_Smallest_Prefix_Arr(arr, root)


class Solution:

	def findPrefixes(self, arr, N):

		class Trienode:

			def __init__(self):
				self.d = {}
				self.f = 0
				self.c = 0

		class Trie:

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

			def insert(self, word):
				p = self.root
				for i in word:
					if i not in p.d:
						p.d[i] = Trienode()
					p.c += 1
					p = p.d[i]
				p.f = 1

			def fp(self, word):
				p = self.root
				pre = ''
				for i in word:
					pre += i
					p = p.d[i]
					ch = list(p.d.items())
					if len(ch) == 1 and p.c == 1:
						return pre
				return pre
		t = Trie()
		for i in arr:
			t.insert(i)
		l = []
		for i in arr:
			l.append(t.fp(i))
		return l


class TrieNode:

	def __init__(self):
		self.links = {}
		self.freq = 0

class Solution:

	def buildTrie(self, word, root):
		for ch in word:
			if ch not in root.links:
				root.links[ch] = TrieNode()
			root.links[ch].freq += 1
			root = root.links[ch]

	def buildPrefix(self, word, root):
		ans = ''
		for ch in word:
			ans += ch
			root = root.links[ch]
			if root.freq == 1:
				break
		return ans

	def findPrefixes(self, arr, N):
		out = []
		root = TrieNode()
		for i in range(N):
			self.buildTrie(arr[i], root)
		for i in range(N):
			out.append(self.buildPrefix(arr[i], root))
		return out


from collections import defaultdict

class Trie:

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

	def insert(self, word):
		cur = self
		for w in word:
			if w not in cur.child:
				cur.child[w] = Trie()
			cur.child[w].freq += 1
			cur = cur.child[w]

class Solution:

	def findPrefixes(self, arr, N):
		res = []
		root = Trie()
		for s in arr:
			root.insert(s)

		def dfs(root, word):
			if not root:
				return
			res = ''
			for i in range(len(word)):
				res += str(word[i])
				if root.child[word[i]].freq == 1:
					break
				root = root.child[word[i]]
			return res
		for i in range(N):
			res.append(dfs(root, arr[i]))
		return res


class Solution:

	def findPrefixes(self, arr, N):
		prefixes = {'': 69}
		indexes = list(range(N))
		result = [None] * N
		l = 0
		while len(arr) > 0:
			for i in range(len(arr) - 1, -1, -1):
				prev_prefix = arr[i][0:l]
				if prefixes[prev_prefix] == 1:
					arr.pop(i)
					pos = indexes.pop(i)
					result[pos] = prev_prefix
					continue
				curr_prefix = prev_prefix + arr[i][l]
				prefixes[curr_prefix] = prefixes.get(curr_prefix, 0) + 1
			l += 1
		return result


from collections import defaultdict

class TrieNode:

	def __init__(self):
		self.children = defaultdict(TrieNode)
		self.count = 0

class Solution:

	def findPrefixes(self, arr, N):
		root = TrieNode()

		def insert(root, word):
			for w in word:
				root = root.children[w]
				root.count += 1
		for word in arr:
			insert(root, word)

		def find(root, word):
			res = []
			for w in word:
				res.append(w)
				root = root.children[w]
				if root.count == 1:
					break
			return ''.join(res)
		return [find(root, x) for x in arr]


class TrieNode:

	def __init__(self):
		self.child = dict()
		self.count = 0
		self.isEnd = False

class Trie:

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

	def insert(self, word):
		pre = self.child
		for c in word:
			pre.count += 1
			pre.child[c] = pre.child.get(c, TrieNode())
			pre = pre.child[c]
		pre.isEnd = True

	def getuniqueprefix(self, word):
		pre = self.child
		ans = ''
		for c in word:
			ans += c
			pre = pre.child[c]
			if pre.count <= 1:
				break
		return ans

class Solution:

	def findPrefixes(self, arr, N):
		trie = Trie()
		for word in arr:
			trie.insert(word)
		unique = []
		for word in arr:
			unique.append(trie.getuniqueprefix(word))
		return unique


class Solution:

	def findPrefixes(self, arr, N):
		z = []
		for i in arr:
			for j in range(len(i)):
				for k in arr[0:arr.index(i)] + arr[arr.index(i) + 1:]:
					try:
						if i[:j + 1] != k[:j + 1]:
							pass
						else:
							break
					except:
						pass
				else:
					z.append(i[:j + 1])
					break
		return z


class TrieNode:

	def __init__(self):
		self.children = {}
		self.wordsInPath = 0

class Trie:

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

	def insert(self, word: str, idx) -> None:
		current = self.root
		for i in word:
			ch = ord(i) - ord('a')
			node = current.children.get(ch)
			if node == None:
				node = TrieNode()
				current.children.update({ch: node})
			current.wordsInPath += 1
			current = node

class Solution:

	def findPrefixes(self, arr, N):
		trie = Trie()
		for i in range(N):
			trie.insert(arr[i], i)

		def bfs(m, word, idx):
			if m.wordsInPath == 1 or idx >= len(word):
				return word[:idx]
			return bfs(m.children[ord(word[idx]) - ord('a')], word, idx + 1)
		final = []
		for i in range(N):
			final.append(bfs(trie.root, arr[i], 0))
		return final


class Trie:

	def __init__(self, words):
		self.root = {}
		for word in words:
			self.add(word)

	def add(self, word):
		curr = self.root
		word += '$'
		for c in word:
			if c not in curr:
				curr[c] = {'count': 0}
			curr = curr[c]
			curr['count'] += 1

	def uniquePrefix(self, word):
		curr = self.root
		result = ''
		for c in word:
			curr = curr[c]
			result += c
			if curr['count'] == 1:
				break
		return result

class Solution:

	def findPrefixes(self, arr, N):
		trie = Trie(arr)
		result = []
		for word in arr:
			result.append(trie.uniquePrefix(word))
		return result


class tire:
	hm = {}
	isend = False
	fre = 0

	def __init__(self, hm, fre, isend):
		self.hm = hm
		self.fre = 0
		self.isend = False

def insert(root, a):
	l = len(a)
	t = root
	for i in range(l):
		ch = a[i]
		if ch in t.hm:
			t = t.hm[ch]
			t.fre += 1
		else:
			nn = tire({}, 0, False)
			t.hm[ch] = nn
			t = nn
			t.fre = 1
	t.isend = True

def search(root, a):
	l = len(a)
	t = root
	pre = []
	for i in range(l):
		ch = a[i]
		if t.hm[ch].fre != 1:
			pre.append(ch)
			t = t.hm[ch]
		else:
			pre.append(ch)
			break
	return ''.join(pre)

class Solution:

	def findPrefixes(self, arr, N):
		res = []
		root = tire({}, 0, False)
		for i in range(N):
			insert(root, arr[i])
		for i in range(N):
			ans = search(root, arr[i])
			res.append(ans)
		return res


from collections import defaultdict

class Solution:

	def findPrefixes(self, arr, N):
		d = defaultdict(int)
		done = [False] * N
		ans = [''] * N
		l = 0
		for el in arr:
			l = max(l, len(el))
		for i in range(l):
			for j in range(N):
				if done[j]:
					continue
				d[arr[j][:i + 1]] += 1
			for j in range(N):
				if not done[j] and d[arr[j][:i + 1]] == 1:
					done[j] = True
					ans[j] = arr[j][:i + 1]
			d = defaultdict(int)
		return ans


class TrieNode:

	def __init__(self):
		self.children = {}
		self.prefixCount = 0

class Solution:

	def findPrefixes(self, arr, N):
		root = TrieNode()
		for word in arr:
			curr = root
			for letter in word:
				if letter not in curr.children:
					curr.children[letter] = TrieNode()
				curr = curr.children[letter]
				curr.prefixCount += 1
		l = []
		for word in arr:
			curr = root
			s = ''
			for letter in word:
				s += letter
				curr = curr.children[letter]
				if curr.prefixCount == 1:
					l.append(s)
					break
		return l


class Node:

	def __init__(self):
		self.link = dict()
		self.ct = 0

class Trie:

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

	def insert(self, word):
		tem = self.root
		for i in word:
			if i not in tem.link:
				tem.link[i] = Node()
			tem.link[i].ct += 1
			tem = tem.link[i]

class Solution:

	def findPrefixes(self, arr, N):
		Root = Trie()
		for word in arr:
			Root.insert(word)
		ans = []
		for word in arr:
			tem = Root.root
			for i in range(len(word)):
				k = word[i]
				if tem.link[k].ct == 1:
					ans.append(word[:i + 1])
					break
				tem = tem.link[k]
		return ans


class TrieNode:

	def __init__(self):
		self.children = {}
		self.freq = 0

class Solution:

	def findPrefixes(self, arr, N):
		root = TrieNode()
		for word in arr:
			ptr = root
			for ch in word:
				if ch not in ptr.children:
					ptr.children[ch] = TrieNode()
				ptr = ptr.children[ch]
				ptr.freq += 1
		(res, count) = (['' for i in range(N)], 0)
		for word in arr:
			(tmp_str, ptr) = ([], root)
			for ch in word:
				ptr = ptr.children[ch]
				tmp_str.append(ch)
				if ptr.freq == 1:
					res[count] = ''.join(tmp_str)
					count += 1
					break
		return res


class TrieNode:

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

	def insertWord(self, word):
		root = self
		for letter in word:
			if letter not in root.children:
				root.children[letter] = TrieNode()
			root.count += 1
			root = root.children[letter]

	def uniqueShortestPrefix(self, word):
		root = self
		res = ''
		for letter in word:
			if root.count == 1:
				return res
			res += letter
			root = root.children[letter]
		return res

class Solution:

	def findPrefixes(self, arr, N):
		TrieDict = TrieNode()
		res = []
		for word in arr:
			TrieDict.insertWord(word)
		for word in arr:
			res.append(TrieDict.uniqueShortestPrefix(word))
		del TrieDict
		return res


class Solution:

	def findPrefixes(self, arr, N):

		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 unique_prefix(s, Trie, path):
			for i in s:
				if i in Trie.child:
					Trie = Trie.child[i]
					path += i
				if Trie.c == 1:
					return path
		Trie = TrieNode()
		for w in arr:
			insert(w, Trie)
		res = []
		for s in arr:
			res.append(unique_prefix(s, Trie, ''))
		return res


class TrieNode:

	def __init__(self):
		self.links = {}
		self.cp = 0

class Trie:

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

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

class Solution:

	def findPrefixes(self, arr, N):
		t = Trie()
		for ele in arr:
			t.insert(ele)
		ans = []
		for ele in arr:
			n = len(ele)
			curr = t.root
			for i in range(n):
				if curr.links[ele[i]].cp == 1:
					ans += [ele[:i + 1]]
					break
				else:
					curr = curr.links[ele[i]]
		return ans


from collections import *

class Node:

	def __init__(self):
		self.child = defaultdict(Node)
		self.cnt = 0

class Solution:

	def findPrefixes(self, a, N):
		q = Node()
		for i in a:
			r = q
			for j in i:
				r = r.child[j]
				r.cnt += 1
		ans = []
		for i in a:
			r = q
			o = 0
			for j in i:
				if r.cnt != 1:
					o += 1
					r = r.child[j]
				else:
					break
			ans += [i[:o]]
		return ans


class Solution:

	def findPrefixes(self, arr, N):

		class TreeNode:

			def __init__(self):
				self.mp = {}
				self.isEnd = False
				self.cnt = 0

		class Trie:

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

			def insert(self, word):
				node = self.root
				for ch in word:
					if ch not in node.mp:
						node.mp[ch] = TreeNode()
					node = node.mp[ch]
					node.cnt += 1
				node.isEnd = True

		def prefix(root, word):
			node = root
			s = ''
			for ch in word:
				node = node.mp[ch]
				if node.cnt == 1:
					s += ch
					return s
				s += ch
		t = Trie()
		for i in arr:
			t.insert(i)
		ans = []
		for i in arr:
			ans.append(prefix(t.root, i))
		return ans


class TrieNode:

	def __init__(self):
		self.children = {}
		self.endOfWord = False
		self.count = 0

class Trie:

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

	def insert(self, word):
		curr = self.root
		for c in word:
			curr.count += 1
			if c not in curr.children:
				curr.children[c] = TrieNode()
			curr = curr.children[c]
		curr.endOfWord = True

	def getUniquePrefix(self, word):
		curr = self.root
		ans = ''
		for c in word:
			ans += c
			curr = curr.children[c]
			if curr.count <= 1:
				break
		return ans

class Solution:

	def findPrefixes(self, arr, N):
		trie = Trie()
		for word in arr:
			trie.insert(word)
		unique = []
		for word in arr:
			unique.append(trie.getUniquePrefix(word))
		return unique


class Node:

	def __init__(self):
		self.arr = {}
		self.cnt = 0
		self.isEnd = False

class Trie:

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

	def insert(self, wd):
		crawler = self.child
		for i in wd:
			idx = ord(i) - ord('a')
			if i not in crawler.arr:
				crawler.arr[i] = Node()
			crawler.arr[i].cnt += 1
			crawler = crawler.arr[i]
		crawler.cnt += 1
		crawler.isEnd = True

	def find(self, wd):
		crawler = self.child
		st = ''
		for i in wd:
			idx = ord(i) - ord('a')
			if crawler.arr[i].cnt == 1:
				st += i
				return st
			st += i
			crawler = crawler.arr[i]
		return st

class Solution:

	def findPrefixes(self, arr, N):
		tr = Trie()
		ans = []
		for i in arr:
			tr.insert(i)
		for i in arr:
			ans.append(tr.find(i))
		return ans


class Trie:

	def __init__(self):
		self.root = [None] * 27

	def add(self, word):
		temp = self.root
		for i in word:
			if temp[ord(i) - 97] == None:
				temp[ord(i) - 97] = [None] * 27
			if temp[26] != None:
				temp[26] += 1
			else:
				temp[26] = 1
			temp = temp[ord(i) - 97]

	def search(self, word):
		temp = self.root
		for (x, i) in enumerate(word):
			if temp[ord(i) - 97] != None:
				temp = temp[ord(i) - 97]
			else:
				return -1
			if temp[26] == 1:
				return x
		return x

class Solution:

	def findPrefixes(self, arr, N):
		trie = Trie()
		for i in arr:
			trie.add(i)
		res = []
		for i in arr:
			ix = trie.search(i)
			res.append(i[:ix + 1])
		return res


class TreeNode:

	def __init__(self):
		self.children = [None] * 26
		self.isEnd = False
		self.isCount = 0

class Solution:

	def insert(self, root, key):
		for level in range(len(key)):
			cur = root.children[ord(key[level]) - ord('a')]
			if cur is None:
				root.children[ord(key[level]) - ord('a')] = TreeNode()
				root.children[ord(key[level]) - ord('a')].isCount += 1
			else:
				root.children[ord(key[level]) - ord('a')].isCount += 1
			root = root.children[ord(key[level]) - ord('a')]
		root.isEnd = True

	def getPrefix(self, root, key):
		ans = ''
		for level in range(len(key)):
			cur = root.children[ord(key[level]) - ord('a')]
			if cur.isCount == 1:
				ans += key[level]
				return ans
			else:
				ans += key[level]
			root = root.children[ord(key[level]) - ord('a')]

	def findPrefixes(self, arr, N):
		index = dict()
		prefix = dict()
		for i in range(len(arr)):
			index[arr[i]] = [i, '']
			if arr[i][0] in prefix:
				prefix[arr[i][0]].append(arr[i])
			else:
				prefix[arr[i][0]] = [arr[i]]
		for k in prefix.keys():
			root = TreeNode()
			for v in prefix[k]:
				self.insert(root, v)
			for v in prefix[k]:
				an = self.getPrefix(root, v)
				index[v][1] = an
		for k in index.keys():
			arr[index[k][0]] = index[k][1]
		return arr


class trienode:

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

class Solution:

	def findPrefixes(self, arr, N):
		root = trienode()
		for word in arr:
			cur = root
			for c in word:
				if c not in cur.children:
					cur.children[c] = trienode()
				cur = cur.children[c]
			cur.isLast = True
		res = []
		for word in arr:
			cur = root
			temp = []
			shortestPrefix = []
			split = False
			for c in word:
				cur = cur.children[c]
				temp.append(c)
				if split:
					shortestPrefix.extend(temp)
					temp = []
					split = False
				if len(cur.children) > 1:
					split = True
			if not shortestPrefix:
				res.append(word[0])
			else:
				res.append(''.join(shortestPrefix))
		return res


class Solution:

	def findPrefixes(self, arr, N):
		s = {}
		for i in arr:
			t = ''
			c = 0
			for j in i:
				t += j
				if t in s:
					s[t] += 1
				else:
					s[t] = 1
				c += 1
				if c == 100:
					break
		b = []
		for i in arr:
			t = ''
			for j in i:
				t += j
				if s[t] == 1:
					b.append(t)
					break
		return b


class Trie:

	def __init__(self, words):
		self.root = {}
		for word in words:
			self.add(word)

	def add(self, word):
		curr = self.root
		word += '$'
		for c in word:
			if c not in curr:
				curr[c] = {'count': 0}
			curr = curr[c]
			curr['count'] += 1

	def uniquePrefix(self, word):
		curr = self.root
		result = ''
		for c in word:
			curr = curr[c]
			result += c
			if curr['count'] == 1:
				break
		return result

class Solution:

	def findPrefixes(self, arr, N):
		trie = Trie(arr)
		result = []
		for word in arr:
			result.append(trie.uniquePrefix(word))
		return result
import sys
sys.setrecursionlimit(10 ** 6)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		arr = list(map(str, input().split()))
		ob = Solution()
		res = ob.findPrefixes(arr, N)
		for i in res:
			print(i, end=' ')
		print()


class Solution:

	def findPrefixes(self, arr, N):
		prefixes = {'': 69}
		indexes = list(range(N))
		result = [None] * N
		l = 0
		while len(arr) > 0:
			for i in range(len(arr) - 1, -1, -1):
				prev_prefix = arr[i][0:l]
				if prefixes[prev_prefix] == 1:
					arr.pop(i)
					pos = indexes.pop(i)
					result[pos] = prev_prefix
					continue
				curr_prefix = prev_prefix + arr[i][l]
				prefixes[curr_prefix] = prefixes.get(curr_prefix, 0) + 1
			l += 1
		return result
import sys
sys.setrecursionlimit(10 ** 6)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		arr = list(map(str, input().split()))
		ob = Solution()
		res = ob.findPrefixes(arr, N)
		for i in res:
			print(i, end=' ')
		print()


from collections import defaultdict

class Solution:

	class Node:

		def __init__(self):
			self.count = 1
			self.children = defaultdict(int)

	class Trie:

		def __init__(self) -> None:
			self.root = Solution.Node()

		def add(self, word):
			curr = self.root
			for char in word:
				if curr.children[char]:
					curr.children[char].count += 1
				else:
					curr.children[char] = Solution.Node()
				curr = curr.children[char]

		def shortest_prefix(self, word):
			prefix = []
			self.__shortest_prefix(self.root, word, 0, prefix)
			return ''.join(prefix)

		def __shortest_prefix(self, node, word, i, prefix):
			if i >= len(word) or not node.children[word[i]]:
				prefix.append('')
				return
			node = node.children[word[i]]
			if node.count == 1:
				prefix.append(word[i])
				return
			prefix.append(word[i])
			self.__shortest_prefix(node, word, i + 1, prefix)
			return

	def findPrefixes(self, arr, N):
		if N == 0:
			return ''
		trie = Solution.Trie()
		prefixes = []
		for word in arr:
			trie.add(word)
		for word in arr:
			prefixes.append(trie.shortest_prefix(word))
		return prefixes
import sys
sys.setrecursionlimit(10 ** 6)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		arr = list(map(str, input().split()))
		ob = Solution()
		res = ob.findPrefixes(arr, N)
		for i in res:
			print(i, end=' ')
		print()


class Node:

	def __init__(self):
		self.children = {}
		self.children_count = 0

class Solution:

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

	def insert(self, word):
		curr = self.root
		for i in word:
			if i in curr.children:
				curr.children_count += 1
				curr = curr.children[i]
			else:
				curr.children_count += 1
				new = Node()
				curr.children[i] = new
				curr = curr.children[i]

	def prefix(self, word):
		str = ''
		curr = self.root
		for i in word:
			if curr.children_count <= 1:
				return str
			else:
				str = str + i
				curr = curr.children[i]
		return str

	def findPrefixes(self, arr, N):
		if N == 1:
			return []
		for i in arr:
			self.insert(i)
		ans = []
		for i in arr:
			ans.append(self.prefix(i))
		return ans
import sys
sys.setrecursionlimit(10 ** 6)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		arr = list(map(str, input().split()))
		ob = Solution()
		res = ob.findPrefixes(arr, N)
		for i in res:
			print(i, end=' ')
		print()


class Node:

	def __init__(self):
		self.children = {}
		self.children_count = 0

class Solution:

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

	def insert(self, word):
		curr = self.root
		for i in word:
			if i in curr.children:
				curr.children_count += 1
				curr = curr.children[i]
			else:
				curr.children_count += 1
				new = Node()
				curr.children[i] = new
				curr = curr.children[i]

	def findPrefix(self, word):
		str = ''
		curr = self.root
		for i in word:
			if curr.children_count <= 1:
				return str
			else:
				str = str + i
				curr = curr.children[i]
		return str

	def findPrefixes(self, arr, N):
		if N == 1:
			return []
		for i in arr:
			self.insert(i)
		ans = []
		for i in arr:
			ans.append(self.findPrefix(i))
		return ans


class Solution:

	def findPrefixes(self, arr, N):
		result = []
		for i in range(N):
			prefix = arr[i][0]
			j = 0
			while j < N:
				if i != j and arr[j][:len(prefix)] == prefix:
					prefix = arr[i][:len(prefix) + 1]
					continue
				j += 1
			result.append(prefix)
		return result


class Trie:

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

	def insert(self, word):
		cur = self
		for c in word:
			if c not in cur.children:
				cur.children[c] = Trie()
			cur = cur.children[c]
			cur.count += 1
		cur.isWord = True

	def search(self, word):
		cur = self.children[word[0]]
		curString = word[0]
		i = 1
		while i < len(word):
			if cur.count == 1:
				return curString
			curString += word[i]
			cur = cur.children[word[i]]
			i += 1
		return word

class Solution:

	def findPrefixes(self, arr, N):
		trie = Trie()
		for word in arr:
			trie.insert(word)
		output = []
		for word in arr:
			prefix = trie.search(word)
			output.append(prefix)
		return output


class TrieNode:

	def __init__(self, node=None, end=False, count=0):
		self.children = {}
		self.end = end
		self.count = count

	def insert(self, root, key):
		curr = root
		for char in key:
			if char not in curr.children:
				new_node = TrieNode()
				new_node.count += 1
				curr.children[char] = new_node
			else:
				curr.children[char].count += 1
			curr = curr.children[char]
		curr.end = True

class Solution:

	def prefix(self, word, root):
		prefix = []
		curr = root
		for char in word:
			if curr.children[char].count != 1:
				prefix.append(char)
				curr = curr.children[char]
			else:
				prefix.append(char)
				break
		return ''.join(prefix)

	def findPrefixes(self, arr, N):
		root = TrieNode()
		curr = root
		ans = []
		for word in arr:
			curr.insert(root, word)
		for word in arr:
			pref = self.prefix(word, root)
			ans.append(pref)
		return ans


class Trie:

	def __init__(self):
		self.root = {}
		self.endSymbol = '*'

	def addWord(self, word):
		currentNode = self.root
		for char in word:
			if char not in currentNode:
				currentNode[char] = {}
			currentNode = currentNode[char]
		currentNode[self.endSymbol] = True

class Solution:

	def findPrefixes(self, arr, N):
		trie = Trie()
		for word in arr:
			trie.addWord(word)
		result = []
		for idx in range(N):
			result.append(self.getShortestUniquePrefix(arr[idx], result, trie))
		return result

	def getShortestUniquePrefix(self, word, result, trie):
		currentNode = trie.root
		index = None
		for (idx, char) in enumerate(word):
			currentNode = currentNode[char]
			if index is None and len(currentNode) <= 1:
				index = idx
			elif len(currentNode) > 1:
				index = None
		return word[:index + 1]


class TrieNode:

	def __init__(self):
		self.children = dict()
		self.count = 0

class Trie:

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

	def insert(self, key):
		current = self.root
		for char in key:
			current.count += 1
			if char not in current.children:
				current.children[char] = TrieNode()
			current = current.children[char]

	def searchForUniquePrefix(self, key):
		current = self.root
		ans = ''
		for char in key:
			if current.count == 1:
				break
			current = current.children[char]
			ans += char
		return ans

class Solution:

	def findPrefixes(self, arr, N):
		prefixes = []
		trie = Trie()
		for word in arr:
			trie.insert(word)
		for word in arr:
			prefixes.append(trie.searchForUniquePrefix(word))
		return prefixes


class TrieNode:

	def __init__(self):
		self.children = {}
		self.endofword = False
		self.count = 0

class Trie:

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

	def insert(self, word):
		cur = self.root
		for i in word:
			if i not in cur.children:
				cur.children[i] = TrieNode()
			cur = cur.children[i]
			cur.count += 1
		self.endofword = True

	def unique(self, word):
		cur = self.root
		ans = ''
		for i in word:
			ans = ans + i
			cur = cur.children[i]
			if cur.count <= 1:
				break
		return ans

class Solution:

	def findPrefixes(self, arr, N):
		trie = Trie()
		for i in arr:
			trie.insert(i)
		uniq = []
		for i in arr:
			uniq.append(trie.unique(i))
		return uniq


class Trie:

	def __init__(self, words):
		self.root = {}
		for i in words:
			self.add(i)

	def add(self, word):
		curr = self.root
		word += '$'
		for c in word:
			if c not in curr:
				curr[c] = {'count': 0}
			curr = curr[c]
			curr['count'] += 1

	def helper(self, word):
		curr = self.root
		res = ''
		for c in word:
			curr = curr[c]
			res += c
			if curr['count'] == 1:
				break
		return res

class Solution:

	def findPrefixes(self, arr, N):
		trie = Trie(arr)
		re = []
		for i in arr:
			re.append(trie.helper(i))
		return re


class Node:

	def __init__(self):
		self.chi = {}
		self.isla = False
		self.co = 0

class trie:

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

	def insert(self, word):
		t = self.root
		for i in range(len(word)):
			t.co += 1
			if t.chi.get(word[i]) is None:
				t.chi[word[i]] = Node()
			t = t.chi[word[i]]
		t.isla = True

	def find(self, word):
		t = self.root
		s = ''
		for i in range(len(word)):
			if t.co == 1:
				return s
			s += word[i]
			t = t.chi[word[i]]
		return s

class Solution:

	def findPrefixes(self, arr, n):
		tr = trie()
		for val in arr:
			tr.insert(val)
		ans = []
		for val in arr:
			ans.append(tr.find(val))
		return ans


class Solution:

	def prefixCount(self, prefix):
		return len([x for x in arr if x.startswith(prefix)])

	def findPrefixes(self, arr, N):
		self.arr = arr
		prefixes = []
		for word in self.arr:
			prefix = ''
			for char in word:
				prefix = prefix + char
				n = self.prefixCount(prefix)
				if n == 1:
					prefixes.append(prefix)
					break
		return prefixes


class TrieNode:

	def __init__(self, ch):
		self.val = ch
		self.next = []
		self.end = False

class Trie:

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

	def insert(self, key):
		root = self.root
		n = len(key)
		for i in range(n):
			nextNode = None
			for node in root.next:
				if node.val == key[i]:
					nextNode = node
					break
			if nextNode == None:
				nextNode = TrieNode(key[i])
				root.next.append(nextNode)
			root = nextNode
			if i == n - 1:
				root.end = True

	def search(self, key):
		curr = key[0]
		root = self.root
		n = len(key)
		for i in range(n):
			if len(root.next) > 1:
				curr = key[:i + 1]
			for node in root.next:
				if node.val == key[i]:
					nextNode = node
					break
			root = nextNode
			if i != n - 1 and root.end == True:
				curr = key[:i + 2]
		return curr if not root.next else key

class Solution:

	def findPrefixes(self, arr, N):
		trie = Trie()
		for x in arr:
			trie.insert(x)
		ans = []
		for x in arr:
			ans.append(trie.search(x))
		return ans


class Trie:

	def __init__(self):
		self.root = TrieNode('root')
		self.words = []

	def addWord(self, word):
		self.words.append(word)
		if not self.root:
			self.root = word[0]
		self._insert1(word)

	def _insert1(self, word):
		currentNode = self.root
		for char in word:
			nodeForChar = currentNode.getChildWithValue(char)
			if nodeForChar is None:
				nodeForChar = TrieNode(char)
			else:
				nodeForChar.increaseCount()
			currentNode.children.append(nodeForChar)
			currentNode = nodeForChar

	def _insert(self, currentNode, word):
		if len(word) == 0:
			return
		newNode = currentNode.getChildWithValue(word[0])
		if newNode is not None:
			newNode.increaseCount()
		else:
			newNode = TrieNode(word[0])
			currentNode.children.append(newNode)
		self._insert(newNode, word[1:])

	def getPrefixes(self):
		return [self.getWordPrefix(word) for word in self.words]

	def getWordPrefix(self, word):
		return self.searchForUnique(self.root.getChildWithValue(word[0]), word, '')

	def searchForUnique(self, node, word, prefix):
		if node.count == 1:
			return '{}{}'.format(prefix, word[0])
		else:
			return self.searchForUnique(node.getChildWithValue(word[1]), word[1:], prefix + word[0])

class TrieNode:

	def __init__(self, value):
		self.value = value
		self.count = 1
		self.children = []

	def hasValue(self, value):
		return self.value == value

	def increaseCount(self):
		self.count = self.count + 1

	def getChildWithValue(self, value):
		for child in self.children:
			if child.hasValue(value):
				return child
		return None

class Solution:

	def findPrefixes(self, arr, N):
		trie = Trie()
		for word in arr:
			trie.addWord(word)
		return trie.getPrefixes()


class Trie:

	def __init__(self):
		self.isEnd = False
		self.chars = {}

class Solution:

	def addToTrie(self, root, word):
		curr = root
		for c in word:
			if c not in curr.chars:
				curr.chars[c] = Trie()
			curr = curr.chars[c]
		curr.isEnd = True

	def getUniquePrefix(self, root, word):
		curr = root
		x = 0
		for c in range(len(word)):
			flag = True
			if len(curr.chars) > 1:
				x = c
			curr = curr.chars[word[c]]
		return word[:x + 1]

	def findPrefixes(self, arr, N):
		root = Trie()
		for w in arr:
			self.addToTrie(root, w)
		res = []
		for w in arr:
			res.append(self.getUniquePrefix(root, w))
		return res


class Node:

	def __init__(self):
		self.next = {}
		self.children = 0
		self.words = 0

class Solution:

	def findPrefixes(self, arr, N):
		root = Node()

		def fun(node, word, i):
			if i == len(word) or node.words == 1:
				return 1
			return 1 + fun(node.next[word[i + 1]], word, i + 1)
		for word in arr:
			node = root
			for letter in word:
				if not node.next.get(letter, None):
					node.next[letter] = Node()
					node.children += 1
				node = node.next[letter]
				node.words += 1
		res = []
		for word in arr:
			node = root.next[word[0]]
			last = fun(node, word, 0)
			res.append(word[:last])
		return res


class Solution:

	def findPrefixes(self, arr, N):
		result = ['' for i in range(N)]
		done = set()
		maxx = 0
		for word in arr:
			if len(word) > maxx:
				maxx = len(word)
		for i in range(maxx):
			for (ind, word) in enumerate(arr):
				if ind not in done:
					result[ind] += word[i]
			hashmap = {}
			for (ind, pref) in enumerate(result):
				if ind not in done:
					if pref not in hashmap:
						hashmap[pref] = 0
					hashmap[pref] += 1
			for (ind, pref) in enumerate(result):
				if ind not in done:
					if hashmap[pref] == 1:
						done.add(ind)
			if len(done) == len(arr):
				break
		return result


class TrieNode:

	def __init__(self, char):
		self.char = char
		self.children = {}
		self.count = 0

class Solution:

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

	def insert(self, string):
		curr = self.root
		for ch in string:
			if ch not in curr.children:
				new = TrieNode(ch)
				curr.children[ch] = new
			curr = curr.children[ch]
			curr.count = curr.count + 1

	def check(self, string):
		curr = self.root
		ans = ''
		for ch in string:
			if ch in curr.children:
				curr = curr.children[ch]
				if curr.count == 1:
					ans = ans + curr.char
					return ans
				else:
					ans = ans + curr.char
		return ans

	def findPrefixes(self, arr, N):
		output = []
		for i in arr:
			self.insert(i)
		for j in arr:
			output.append(self.check(j))
		return output


class TrieNode:

	def __init__(self):
		self.children = dict()
		self.freq = 0

class Solution:

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

	def insert(self, arr):
		for word in arr:
			curr = self.root
			for w in word:
				if w not in curr.children:
					curr.children[w] = TrieNode()
				curr = curr.children[w]
				curr.freq += 1

	def findPrefixes(self, arr, N):
		self.insert(arr)
		result = []
		for word in arr:
			curr = self.root
			prefix = ''
			for w in word:
				prefix += w
				if curr.children[w].freq == 1:
					result.append(prefix)
					break
				else:
					curr = curr.children[w]
		return result


class TrieNode:

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

class Solution:

	def findPrefixes(self, arr, N):
		root = TrieNode()
		root.count = float('inf')
		for word in arr:
			cur = root
			for char in word:
				if char not in cur.children:
					cur.children[char] = TrieNode()
				cur = cur.children[char]
				cur.count += 1
		res = []
		for word in arr:
			string = ''
			cur = root
			for char in word:
				cur = cur.children[char]
				string += char
				if cur.count == 1:
					res.append(string)
					break
		return res