Python Recursive without separate Node class


  • 0
    A

    I feel we don't really need to create a new class as trie node. Every node can be viewed as a new trie itself. The code for this implementation is given below:

    class Trie(object):
    
        def __init__(self):
            """
            Initialize your data structure here.
            """
            self.nextptr = [None]*26
            self.end= False
    
        def insert(self, word, index = 0):
            """
            Inserts a word into the trie.
            :type word: str
            :rtype: void
            """
            if index == len(word): 
                self.end = True 
                return
            if not self.nextptr[ ord(word[index])-ord('a') ]: self.nextptr[ ord(word[index])-ord('a') ] = Trie()
            self.nextptr[ ord(word[index])-ord('a') ].insert(word, index+1)
            return
    
        def search(self, word, index = 0):
            """
            Returns if the word is in the trie.
            :type word: str
            :rtype: bool
            """
            if len(word) == index: return True if self.end else False
            if not self.nextptr[ ord(word[index])-ord('a') ]: return False
            return self.nextptr[ ord(word[index])-ord('a') ].search( word, index+1 )
    
        def startsWith(self, prefix, index=0):
            """
            Returns if there is any word in the trie that starts with the given prefix.
            :type prefix: str
            :rtype: bool
            """
            if len(prefix) == index: return True
            if not self.nextptr[ ord(prefix[index])-ord('a') ]: return False
            return self.nextptr[ ord(prefix[index])-ord('a') ].startsWith( prefix, index+1 )
            
    
    
    # Your Trie object will be instantiated and called as such:
    # obj = Trie()
    # obj.insert(word)
    # param_2 = obj.search(word)
    # param_3 = obj.startsWith(prefix)
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.