Python Recursive without separate Node class

  • 0

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