14. Longest Common Prefix

Find the problem description here.

https://leetcode.com/problems/longest-common-prefix/

Solution

Using Naive Pointer Approach.

Approach 1:

Find the shortest string in the array. Then run a main for loop till the length of this shortest string. And for each iteration we are checking for all the strings in the array, if the character at that index position is same for all string. Else we return the longest prefix found so far.

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

Time :O(n*m) n ->total umber of strings, m ->length of shortest string

Space : O(1)

Approach 2:

Using trie

Insert all character in the trie, here a node contain a prefix variable , which keep the count of prefix . After inserting choose any one of the string in the given array and move through the nodes till the prefix count of current node is =length of the strs array(that is this is the longest common prefix for all the string in the strs array)

#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)))

Time :O(n*m) n ->total umber of strings, m ->length of shortest string

Space : O(1) (specifically speaking , the total number of character for all the strings in the strs array)