208. Implement Trie (Prefix Tree)

Check out the problem description here.

Implement Trie (Prefix Tree) - LeetCode

class Node:
    def __init__(self):
        self.arr=[None for i in range(26)]
        self.flag=False
    def contains(self,letter):
        return self.arr[ord(letter)-97]!=None    
    def put(self,letter , node):
        self.arr[ord(letter)-97]=node
    def get(self,letter):
        return self.arr[ord(letter)-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: str) -> None:
        temp =self.root
        for i in word :
            if not temp.contains(i):
                temp.put(i,Node())
            temp=temp.get(i)    
        temp.setEnd()    
    def search(self, word: str) -> bool:
        temp =self.root
        for i in word :
            if not temp.contains(i):
                return False
            temp=temp.get(i)    
        return temp.getEnd()    
    def startsWith(self, prefix: str) -> bool:
        temp =self.root
        for i in prefix :
            if not temp.contains(i):
                return False
            temp=temp.get(i)    
        return True

insert :O(len(word))

search:O(len(word))

startwith:O(len(word))

Space Complexity :

insert :O(len(word))

search: O(1)

startwith: O(1)