#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/data-structures/tries/problem-add-and-search-word

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░██████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/data-structures/tries/problem-add-and-search-word

Repovive

Problem - Add and Search Word - Tries | Data Structures | Repovive

Repovive.

Data Structures19 sections · 729 units49h total

Open in Course

Problem - Add and Search Word

Trie with wildcards

Design a data structure that supports:

addWord(word): Add word to the structure
search(word): Return true if word matches. Word may contain '.' which matches any letter.

Example:

addWord("bad")
addWord("dad")
search("pad")  // false
search("bad")  // true
search(".ad")  // true
search("b..")  // true

This extends the basic trie with wildcard matching, requiring backtracking when you encounter '.'.

Constraints: words are lowercase letters only, '.' only appears in search queries, up to $10^4$ operations.