\

Design Add And Search Words Data Structure

Difficulty: N/A | Solved: December 20, 2025

Problem

Design a data structure that supports adding new words and finding if a string matches any previously added string.

Implement the WordDictionary class:

  • WordDictionary() Initialises the object.
  • void addWord(word) Adds word to the data structure, it can be matched later.
  • bool search(word) Returns true if there is any string in the data structure that matches word or false otherwise. word may contain dots '.' where dots can be matched with any letter.

Example:

Input ["WordDictionary","addWord","addWord","addWord","search","search","search","search"] [[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]] Output [null,null,null,null,false,true,true,true]

Explanation WordDictionary wordDictionary = new WordDictionary(); wordDictionary.addWord(“bad”); wordDictionary.addWord(“dad”); wordDictionary.addWord(“mad”); wordDictionary.search(“pad”); // return False wordDictionary.search(“bad”); // return True wordDictionary.search(".ad"); // return True wordDictionary.search(“b..”); // return True

Brainstorming

Brute force

So this looks like a problem which we can solve with Tries A Trie is a special kind of prefix tree that has at every node 2 information

  1. the next neighbour character and its node eg {“c”:node_c}
  2. a boolean flag that tells if its an end of a word eg: is_complete = True or false

so we would need 2 things to solve this problem

  1. a class to define a trie node
  2. a class to execute the add and search operation
class TrieNode:
	def __init__(self, neighbours={}, is_complete=False):
		self.neighbours = neighbours
		self.is_complete = is_complete

class WordDictionary:
	def __init(self):
		self.head = TrieNode()
	
	def add_word(self, word):
		curr = self.head
		for char in word:
			if char not in curr.neighbour:
				char_node = TrieNode()
				curr.neighbour.update({char: char_node})
			curr = curr.neighbour[char]
		curr.is_complete = True
		
	def search_word(self, word):
		curr = self.head
		for char in word:
			if char not in curr.neighbour:
				return False
			curr = curr.neighbour[char]
			
		return True if curr.is_complete else False
		

word_dictionary = WordDictionary()
word_dictionary.add_word("bad")

lets take an example for add word “bad” we get the head the for b a d we check the neighbour

  1. b in neighbour : No -> we make a trie node and add it to the neighbour of
    1. head -> "b" ``
    2. we move the current pointer to b
  2. we check if a is in the neighbour of b : No. -> we make a trie node for A and add it to the neighbour of b
  • 🍅 (pomodoro::WORK) (duration:: 20m) (begin:: 2025-12-15 10:48) - (end:: 2025-12-15 11:08)

Optimal Solution

This is a superb start. Your understanding of Tries is perfect, and you’ve correctly implemented the TrieNode class and the standard add_word function. You’ve also written a correct search_word function for words without a dot (.).

You have successfully built the foundation. Now, let’s focus on the special requirement of this problem: handling the . wildcard.

Your current search_word function needs to be adapted.

def search_word(self, word):
    curr = self.head
    for char in word:
        if char not in curr.neighbour: # What if char is '.'?
            return False
    return True # This only checks if the word is a prefix, not a complete word.

Challenge #1: The . Wildcard

When your search loop encounters a . character, it can match any character. This means you can’t just check curr.neighbour['.']. You need to explore all possible paths from the current node.

  • If char is ., you need to check every neighbor in curr.neighbours.
  • For each neighbor, you need to recursively search for the rest of the word starting from that neighbor node.
  • If any of those recursive searches find a match, then the overall search is successful.

This sounds like a job for recursion!

Challenge #2: Checking for a Complete Word

Your search_word currently returns True if “apple” is in the Trie and you search for “app”. It only checks for a prefix.

  • Question: After the loop finishes successfully, what property of the final curr node do you need to check to ensure you’ve found a complete word and not just a prefix?

Let’s design the new search function.

Because of the . wildcard, the search is no longer a simple loop. It needs to be a recursive helper function (let’s call it dfs_search).

dfs_search(node, word_suffix)

  • node: The TrieNode we are currently at in our search.
  • word_suffix: The remaining part of the word we are trying to match.

Logic for dfs_search(node, word_suffix):

  1. Iterate: Loop through the word_suffix character by character, with an index. Let the current node be curr = node.
  2. For each char at index:
    • If char is a .:
      • You must try all of curr.neighbours.
      • For each neighbor_node in curr.neighbours.values():
        • Make a recursive call: dfs_search(neighbor_node, rest_of_the_word).
        • If any of these recursive calls returns True, then you’ve found a match. Return True immediately.
      • If you loop through all neighbors and none of them lead to a solution, this path fails. Return False.
    • If char is a normal letter:
      • Check if char is in curr.neighbours.
      • If not, this path fails. Return False.
      • If it is, update curr to the next node: curr = curr.neighbours[char]. Continue the loop.
  3. Base Case / After the Loop: If the loop completes successfully (you’ve matched all characters in word_suffix), what do you need to check on the final curr node to confirm it’s a complete word?

(Prompt): Based on this logic, try to write the dfs_search helper function. The trickiest part is the if char == '.' block. How do you handle the recursive calls and their return values?

Okay so first we need to fix the standard search method by adding a check for checking the boolean flag is complete for true along with that an implementation of the dfs search recursive helper

class TrieNode:
	def __init__(self, neighbours={}, is_complete=False):
		self.neighbours = neighbours
		self.is_complete = is_complete

class WordDictionary:
	def __init(self):
		self.head = TrieNode()
	
	# recursive helper 
	def dfs_search(self, node, suffix):
		curr = node	# get the current node
		# for each char and index in current suffix 
		for index, char in enumerate(suffix):
			if char == ".": # if the character is wild card
				# check for each neighbour of the char
				for neighbour_node in curr.neighbours.values():
					# run a recursive DFS search for the neighbour node and the remaining suffix
					match = self.dfs_search(neighbour_node, suffix[index:])
					# if any of the recursive result find the word
					if match:
						return True # return True immediately 
				return False
			elif char not in curr.neighbours: # if its a normal char check if its in the neighbours , if its not then return False immediately
				return False
			else:# if the char is in the neighbour then we can just advance the current pointer to the next neighbour 
				curr = curr.neighbour[char]
		# global boolean return if the current node is a complete node or return False 
		return True if curr.is_complete else False
	
	def add_word(self, word):
		curr = self.head
		for char in word:
			if char not in curr.neighbour:
				char_node = TrieNode()
				curr.neighbour.update({char: char_node})
			curr = curr.neighbour[char]
		curr.is_complete = True
		
	def search_word(self, word):
		curr = self.head
		
		return self.dfs_search(curr,word)
		

word_dictionary = WordDictionary()
word_dictionary.add_word("bad")

This is an excellent implementation. You’ve correctly identified the need for a recursive DFS and have structured it almost perfectly. Your logic for the . wildcard is spot on.

You’ve just made one tiny, but very common, mistake inside the recursive call.

Let’s look at this block:

if char == ".":
    for neighbour_node in curr.neighbours.values():
        # The problem is on the next line
        match = self.dfs_search(neighbour_node, suffix[index:]) 
        if match:
            return True
    return False

Let’s trace search("b.d")

  1. dfs(head, "b.d") starts.
  2. char is ‘b’. This is not ‘.’. curr advances to the ‘b’ node. The loop continues.
  3. char is now ‘.’. index is 1.
  4. The if char == "." block runs.
  5. It loops through the neighbors of the ‘b’ node (let’s say they are ‘a’ and ‘o’ for “bad” and “bod”).
  6. It takes the first neighbor, the ‘a’ node.
  7. It makes the recursive call: self.dfs_search(a_node, suffix[index:]).
    • What is suffix[index:]? index is 1, so it’s ".d".
    • The call is self.dfs_search(a_node, ".d").

The Bug: The recursive call is asked to search for ".d", but it should be searching for the rest of the word after the current character. The . corresponds to the a we are now at. The rest of the word is just 'd'.

The loop inside dfs_search and the recursion are fighting each other. The for loop is trying to manage advancing through the word, but so is the recursion. We should let only the recursion handle advancing through the word.

A simpler structure for a recursive function: A recursive function should typically only handle one step (one character) and then pass the rest of the work (word[1:]) to the next recursive call. It shouldn’t contain a for loop that iterates through the word itself.

Revised Logic for dfs_search(node, word):

  1. Base Case: If the word is empty, what have we successfully matched? The whole thing. What do we need to check on the current node?

  2. Recursive Step:

    • Take the first character of the word, char = word[0].
    • Take the rest of the word, rest = word[1:].
    • If char is a .:
      • Loop through all neighbors of the current node.
      • For each neighbor, recursively call dfs_search(neighbor, rest).
      • If any call returns True, return True.
    • If char is a normal letter:
      • Check if char is a neighbor of the current node.
      • If yes, recursively call dfs_search on that neighbor with rest.
      • If no, return False.

(Prompt): Rewrite your dfs_search function using this simpler structure. Let the recursion handle advancing through the word by passing word[1:] each time, instead of using an outer for loop.

class TrieNode:
	def __init__(self, neighbours={}, is_complete=False):
		self.neighbours = neighbours
		self.is_complete = is_complete
		
class WordDictionary:

	def __init__(self):
		self.head = TrieNode()
	
	def dfs_search(self, node, suffix):
		curr = node
		# Base case # when we reach the end of the word
		if not suffix: 
			if curr.is_complete:
				return True
			else:
				return False
		
		char = suffix[0]
		rest = suffix[1:]
		
		if char == ".":
			for neighbour in curr.neighbours.values():
				word_found = self.dfs_search(neighbour, rest)
				if word_found:
					return True
			return False # if all the recursive call fail after the wild card search that means the word is not there in the trie hence we should immediately return False
	
		elif char not in curr.neighbours: # if its a normal char check if its in the neighbours , if its not then return False immediately
			return False
		else:
			# advance the current pointer recursively
			# see if we find the word or not return its result 
			return self.dfs_search(curr.neighbours[char], rest)
		
	def add_word(self, word):
		curr = self.head
		for char in word:
			if char not in curr.neighbours:
				char_node = TrieNode()
				curr.neighbours.update({char: char_node})
			curr = curr.neighbours[char]
		curr.is_complete = True
		
	def search_word(self, word):
		curr = self.head
		
		return self.dfs_search(curr,word)



word_dictionary = WordDictionary()
word_dictionary.add_word("bad")
print(word_dictionary.search_word("bad"))
  • 🍅 (pomodoro::WORK) (duration:: 30m) (begin:: 2025-12-15 11:09) - (end:: 2025-12-15 11:58)