DSAPrep
MediumTries

Design Add And Search Words Data Structure

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

Implement the WordDictionary class:

WordDictionary() Initializes 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 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]
Explanation: wordDictionary.addWord("bad"); wordDictionary.addWord("dad"); wordDictionary.addWord("mad"); search("pad") returns false (never added); search("bad") returns true; search(".ad") returns true (the dot matches "b", "d", or "m"); search("b..") returns true (both dots match "a" and "d").

Constraints

  • 1 <= word.length <= 25
  • word in addWord consists of lowercase English letters.
  • word in search consist of '.' or lowercase English letters.
  • There will be at most 2 dots in word for search queries.
  • At most 10^4 calls will be made to addWord and search.
View original on LeetCode ā†—

This is the same trie as Implement Trie Prefix Tree, plus one wrinkle: search can contain . wildcards that match any single character. A plain iterative walk cannot handle that, because a . might need to try several children before one of them leads to a match ā€” so search becomes a small DFS over the trie instead of a straight-line walk.

Brute Force: Words Grouped by Length

Time addWord O(L), search O(nĀ·L)Space O(nĀ·L)

Since a . matches exactly one character, a query can only ever match words of the same length. Bucket stored words by length, then for a query, scan only the bucket of matching length and compare position by position, treating . as a wildcard.

from collections import defaultdict


class WordDictionary:
    def __init__(self):
        self.by_len = defaultdict(list)


    def addWord(self, word: str) -> None:
        self.by_len[len(word)].append(word)


    def search(self, word: str) -> bool:
        for candidate in self.by_len[len(word)]:
            if all(w == '.' or w == c for w, c in zip(word, candidate)):
                return True
        return False

Grouping by length prunes obviously-wrong candidates, but within a bucket every word is still compared character by character in the worst case ā€” O(nĀ·L) for a search that matches late or not at all, where n is the number of words of that length.

Trie + DFS for Wildcards

OptimalTime addWord O(L), search O(26^d Ā· L)Space O(total characters inserted)

Store words in a trie exactly as before. addWord is the same walk-and-create as insert. search also walks the trie, but on a . it cannot pick one child ā€” it must try every child at that position and succeed if any of them leads to a full match. That is a DFS with backtracking, not a loop.

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


class WordDictionary:
    def __init__(self):
        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(node, i):
            if i == len(word):
                return node.is_word
            ch = word[i]
            if ch == '.':
                return any(dfs(child, i + 1) for child in node.children.values())
            if ch not in node.children:
                return False
            return dfs(node.children[ch], i + 1)


        return dfs(self.root, 0)

Tracing addWord("bad"), addWord("dad"), addWord("mad") ā€” three separate root branches, since they differ in their first letter ā€” then a few searches:

ā€¢
1 / 8
comparingresultdiscarded

Start with an empty trie: just the root.

Complexity: addWord is O(L), unchanged from a plain trie. search is O(L) when there are no dots, but each dot can branch into up to 26 children, so a query with d dots costs O(26^d Ā· L) in the worst case. The constraints cap dots at 2 per query, which keeps this fast in practice even though the theoretical worst case has exponential branching.