14. Longest Common Prefix

class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
length=500
for i in strs:
if(len(i)<length):
length=len(i)
result=""
for i in range(length):
curr_character= strs[0][i]
for j in strs:
if(j[i]!=curr_character):
return result
result+=strs[-1][i]
return result
#trie
class Node:
def __init__(self):
self.arr=[None for i in range(26)]
self.flag=False
self.prefix=0
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.prefix+=1
temp.setEnd()
def longest(self,sample,arraylength):
result=""
temp=self.root
for i in sample:
temp=temp.get(i)
print(temp)
if(temp.prefix==arraylength):
result+=i
else:
break

return result

class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
trie = Trie()
for i in strs:
trie.insert(i)
sample=strs[-1]
return(trie.longest(sample,len(strs)))

--

--

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.