Add and Search Word - Data structure design
Problem: Add and Search Word - Data structure design
I use a trie to solve the problem, as what the hints say. However, there's other faster solution using hash table.
Code in Python:
class TrieNode(object):
def __init__(self):
self.isWord = False
self.children = [None] * 26
class Trie(object):
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for c in word:
if not node.children[ord(c)-ord('a')]:
node.children[ord(c)-ord('a')] = TrieNode()
node = node.children[ord(c)-ord('a')]
node.isWord = True
class WordDictionary(object):
def __init__(self):
"""
initialize your data structure here.
"""
self.trie = Trie()
def addWord(self, word):
"""
Adds a word into the data structure.
:type word: str
:rtype: void
"""
self.trie.insert(word)
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(self.trie.root, word)
def search_helper(self, node, word):
if not word:
if node.isWord: return True
else: return False
if word[0] == '.':
for child in node.children:
if child and self.search_helper(child, word[1:]): return True
return False
else:
if node.children[ord(word[0])-ord('a')]: return self.search_helper(node.children[ord(word[0])-ord('a')], word[1:])
else: return False