simple trie python solution


  • 0
    Z
    class Trie(object):
    
        def __init__(self):
            self.children = [None] * 27
    
        def add(self, word):
            if not word:
                self.children[26] = Trie()
                return
            w = word[0]
            ind = ord(w) - ord('a')
            if not self.children[ind]:
                self.children[ind] = Trie()
            self.children[ind].add(word[1:])
    
        def has(self, word):
            if not word:
                return self.children[26] != None
            w = word[0]
            if w == '.':
                for child in self.children:
                    if child and child.has(word[1:]):
                        return True
                return False
            ind = ord(w) - ord('a')
            if self.children[ind]:
                return self.children[ind].has(word[1:])
            else:
                return False
                
    class WordDictionary(object):
        def __init__(self):
            self.trie = Trie()
            
        def addWord(self, word):
            self.trie.add(word)
            
        def search(self, word):
            return self.trie.has(word)

Log in to reply
 

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