hello every , i tried to solve ENGRIS using Trie ,but got WA.
will u plz help me with this?
my submitted code
works fine with given test case and with a bunch i tried with .
thanks a ton in advance…
import collections
class TrieNode:
def __init__(self):
self.char=collections.defaultdict(TrieNode)
self.isEnd=False
class Trie:
def __init__(self):
self.root=TrieNode()
def insert(self,word):
curr=self.root
for l in word:
curr=curr.char[l]
curr.isEnd=True
def match(self,node,string):
for l in string:
node=node.char.get(l)
if not node:
return False
return node.isEnd
def isPresent(self,string):
curr=self.root
for l in range(len(string)):
if string[l] in curr.char:
curr=curr.char[string[l]]
else:
for ch in curr.char:
new=curr.char[ch]
if self.match(new,string[l:]):
return string[:l]+ch+string[l:]
elif self.match(new,string[l+1:]):
return string[:l]+ch+string[l+1:]
if(curr.isEnd):
return string
for c in curr.char:
if self.match(curr.char[c],""):
return string+c
t=int(input())
for _ in range(t):
t=Trie()
n,q=map(int,input().split())
for __ in range(n):
t.insert(input())
for ___ in range(q):
print(t.isPresent(input()))
