Skip to main content
CodeEasy v0.1

Design Add and Search Words Data Structure

Medium Subject: Tries
Time Complexity
O(N * 26^M)
Space Complexity
O(N)

Problem Description

Problem Statement

Design a data structure that supports adding new words and finding if the string matches any previously added string. search(word) can search a literal word or a regular expression string containing only letters a-z or .. The . can match any letter.

Example 1:

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

Optimal Solution

Python

Approach: Trie with DFS for Wildcards

Similar to a standard Trie. For search, if the character is a ., we must recursively check all children in the current node's dictionary. If it's a normal character, we just traverse down.

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

class WordDictionary:
    def __init__(self):
        self.root = TrieNode()

    def addWord(self, word: str) -> None:
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end = True

    def search(self, word: str) -> bool:
        def dfs(j, node):
            for i in range(j, len(word)):
                char = word[i]
                if char == '.':
                    for child in node.children.values():
                        if dfs(i + 1, child):
                            return True
                    return False
                else:
                    if char not in node.children:
                        return False
                    node = node.children[char]
            return node.is_end

        return dfs(0, self.root)