Longest String with All Prefixes

from typing import *class Node:
def __init__(self):
self.arr=[None for i in range(26)]
self.flag=False
def contains(self,i):
return self.arr[ord(i)-97]!=None
def put(self,i):
self.arr[ord(i)-97]=Node()
def get(self,i):
return(self.arr[ord(i)-97])
def setEnd(self):
self.flag=True
def getEnd(self):
return self.flag==True

class Trie:
def __init__(self):
self.root=Node()
def insert(self,word):
temp=self.root
for i in word:
if not temp.contains(i):
temp.put(i)
temp = temp.get(i)
temp.setEnd()

def complete(self,word):
temp=self.root
for i in word:
if temp.arr[ord(i)-97] and temp.get(i).getEnd():
temp=temp.get(i)
else:
return False
return True

def completeString(n: int, a: List[str])-> str:
trie = Trie()
longest=""
for i in range(n):
trie.insert(a[i])
for i in range(n):
if(trie.complete(a[i])):
if(len(longest)<len(a[i])):
longest=a[i]
elif(len(longest)==len(a[i])):
if(longest>a[i]):
longest=a[i]

return(longest if longest!="" else None)

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Dhanarajappu

Dhanarajappu

Tech-Enthusiast, Coder,Explorer,Geeky,Software Engineer |A piece of code delivers everything that you need. The world is all about codes.