Question: https://leetcode.com/problems/add-and-search-word-data-structure-design/
Question Name: Add and Search Word – Data Structure Design
This is a variant of prefix tree (trie).
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 | class TrieNode(object): def __init__(self): """ Initialize your data structure here. """ self.isWord = False self.sons = {} class WordDictionary(object): def __init__(self): """ initialize your data structure here. """ self.root = TrieNode() def addWord(self, word): """ Adds a word into the data structure. :type word: str :rtype: void """ current = self.root for letter in word: if letter not in current.sons: current.sons[letter] = TrieNode() current = current.sons[letter] current.isWord = True return def search(self, word): """ Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. :type word: str :rtype: bool """ return self.search_helper(word, self.root) def search_helper(self, word, node): """ Returns if the word is in current trie. A word could contain the dot character '.' to represent any one letter. :type word: str :type node: TrieNode :rtype: bool """ if len(word) == 0: return node.isWord elif word[0] == ".": for candidate in node.sons: if self.search_helper(word[1:], node.sons[candidate]): return True else: return False else: if word[0] in node.sons: return self.search_helper(word[1:], node.sons[word[0]]) else: return False # Your WordDictionary object will be instantiated and called as such: # wordDictionary = WordDictionary() # wordDictionary.addWord("word") # wordDictionary.search("pattern") |