Augmented Trie Solution Python

  • 0

    I say augmented because I'm generating a Trie structure for each word length. It will take up more space scaling by the number of distinct word lengths in the dictionary, but the search will be more efficient.

        def __init__(self):
            self._trie = {}
        def buildDict(self, dict):
            for w in dict:
                if len(w) not in self._trie: self._trie[len(w)] = {} # add new trie
                itr = self._trie[len(w)]
                for c in w:
                    if c not in itr: itr[c] = {} # generate following node
                    itr = itr[c]        
        def trie_search(self, word, i, change, itr):
            if i == len(word): return change
            return any(c == word[i] and self.trie_search(word, i+1, change, itr[c])
                       or c != word[i] and not change and self.trie_search(word, i+1, True, itr[c])
                       for c in itr)
        def search(self, word):
            if len(word) not in self._trie: return False
            return self.trie_search(word, 0, False, self._trie[len(word)])

Log in to reply

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