Add & Search Words 25 XP Medium

LeetCode Ctrl+Enter Run Ctrl+S Save

Design a data structure supporting addWord and search. The search can contain '.' which matches any single character.

Trie + DFS. When we encounter '.', try all children recursively.

💡 Pro tip: Understand this problem deeply — don't just memorize the code. Try explaining the approach out loud as if teaching a friend. If you can explain it simply, you truly understand it!

📋 Instructions

Add words ['bad','dad','mad'], then search: 'pad'→False, 'bad'→True, '.ad'→True, 'b..'→True

In search DFS: if char is '.', loop through all children and recurse. If any returns True, return True.

🧪 Test Cases

Input

wd.search('pad')

Expected

False

Boolean check

Input

wd.search('bad')

Expected

True

Boolean check

Input

wd.search('.ad')

Expected

True

Boolean check

Input

wd.search('b..')

Expected

True

Boolean check

← Previous Next Exercise →

main.py

Hi! I'm Rex 👋

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

class WordDictionary:
    def __init__(self):
        self.root = TrieNode()
    
    def addWord(self, word):
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.is_end = True
    
    def search(self, word):
        def dfs(node, i):
            if i == len(word):
                return node.is_end
            if word[i] == '.':
                for child in node.children.values():
                    if dfs(child, i + 1):
                        return True
                return False
            if word[i] not in node.children:
                return False
            pass  # Continue to next char
        return dfs(self.root, 0)

wd = WordDictionary()
for w in ['bad','dad','mad']:
    wd.addWord(w)
print(wd.search('pad'))
print(wd.search('bad'))
print(wd.search('.ad'))
print(wd.search('b..'))

Output

Ready. Press ▶ Run or Ctrl+Enter.

›