#211MediumTries

Design Add and Search Words Data Structure

The tell: Trie lookup where '.' matches any single character.

How you get there

1Exact characters walk down one child as usual.
2A wildcard must try every child, so the search becomes a DFS.
3Recursion carries the current node and the position in the pattern.

Solution

Python

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

    def addWord(self, word: str) -> None:
        node = self.root
        for ch in word:
            node = node.children.setdefault(ch, TrieNode())
        node.is_word = True

    def search(self, word: str) -> bool:
        def dfs(index: int, node) -> bool:
            for i in range(index, len(word)):
                ch = word[i]
                if ch == ".":
                    return any(dfs(i + 1, child) for child in node.children.values())
                if ch not in node.children:
                    return False
                node = node.children[ch]
            return node.is_word

        return dfs(0, self.root)

Time: O(len(word)) typical, O(26^k) with k wildcards
Space: O(total characters)

What goes wrong

Returning early inside the wildcard branch without `any` reports False as soon as one child fails.

Test yourself on DSA Next: Word Search II →