Implement Trie ii

Implement a data structure ”TRIE” from scratch. Complete some functions.

1) Trie(): Initialize the object of this “TRIE” data structure.

2) insert(“WORD”): Insert the string “WORD” into this “TRIE” data structure.

3) countWordsEqualTo(“WORD”): Return how many times this “WORD” is present in this “TRIE”.

4) countWordsStartingWith(“PREFIX”): Return how many words are there in this “TRIE” that have the string “PREFIX” as a prefix.

5) erase(“WORD”): Delete this string “WORD” from the “TRIE”.

Note:

1. If erase(“WORD”) function is called then it is guaranteed that the “WORD” is present in the “TRIE”.

2. If you are going to use variables with dynamic memory allocation then you need to release the memory associated with them at the end of your solution.

Example:
Input: 
1
6
insert samsung
insert samsung
insert  vivo
erase vivo
countWordsEqualTo samsung
countWordsStartingWith vi
Output: 
2
0
Explanation: 
Insert “samsung”: we are going to insert the word “samsung” into the “TRIE”.
Insert “samsung”: we are going to insert the word “samsung” again into the “TRIE”.
Insert “vivo”: we are going to insert the word “vivo” into the “TRIE”.
Erase “vivo”: we are going to delete the word “vivo” from the “TRIE”.
countWordsEqualTo “samsung”: There are two instances of “samsung” is present in “TRIE”.
countWordsStartWith “vi”:There is not a single word in the “TRIE” that starts from the prefix “vi”.

Solution

class Node:
    def __init__(self):
        self.arr = [None for i in range(26)]
        self.prefix=0
        self.flag=False
        
    def contains(self,character):
        if(self.arr[ord(character)-97]):
            return True
    def get(self,character):
        return(self.arr[ord(character)-97])
    def setEnd(self):
        self.flag=True
    def getEnd(self):
        return self.flag==True
    def put(self, character):
        self.arr[ord(character)-97]=Node()
       
    
class Trie:
    def __init__(self) :
        self.root=Node()
        
    
    def insert(self, string) :
        temp = self.root 
        for i in string:
            if not temp.contains(i):
             temp.put(i)
            temp=temp.get(i)
            temp.prefix+=1
        temp.setEnd()
def countWordsEqualTo(self, word):
        temp = self.root 
        for i in word:
            if not temp.contains(i):
             return 0
            temp=temp.get(i)
        if temp.getEnd() :
            return temp.prefix
def countWordsStartingWith(self, word):
        temp = self.root 
        for i in word:
            if not temp.contains(i):
             return 0
            temp=temp.get(i)
        return temp.prefix
def erase(self, word):
        temp = self.root 
        for i in word:
            if temp.contains(i):    
                temp=temp.get(i)
                temp.prefix-=1

Time : O(n) n ->length of longest word that we are inserting in to the trie

Space: O(1) , Actually the space depends on the input or word that we insert in to the Trie , if the word that we insert in to the trie doesn’t have any common prefix with the already inserted word , then we can say that the space depends on the length of the word being inserted. But at max we can assume the space goes like 26*26*26… till the length of longest word. But for trie , as we can’t accurately predict the space , it is assumed to be constant space.