Design a data structure that supports adding words and searching for them.

Question

Anonymous · Accepted Answer

class TrieNode:

def init(self):

# Stores child nodes where key is the character and value is the TrieNode

self.children = {}

# True if the node represents the end of a complete word

self.is [http://self.is]_end_of_word = False

class WordDictionary:

def init(self):

self.root = TrieNode()

def add_word(self, word: str) -> None:

"""Inserts a word into the data structure."""

current = self.root

for char in word:

# If the character path doesn't exist, create a new node

if char not in current.children:

current.children[char] = TrieNode()

current = current.children[char]

# Mark the end of the word

current.is [http://current.is]_end_of_word = True

def search(self, word: str) -> bool:

"""Returns True if the word is in the data structure, False otherwise."""

current = self.root

for char in word:

# If a character in the sequence is missing, the word doesn't exist

if char not in current.children:

return False

current = current.children[char]

# Return True only if it's marked as a complete word

return current.is [http://current.is]_end_of_word