Longest String with All Prefixes

Find problem description here

Complete String for coding interview round

Solution

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)

Time O(N) n ->length of longest word that we inserted in a test case

Space O(1)