DevOps NetworkDevOpsNetwork
Join Free
Advanced

Design Add and Search Words Data Structure

mediumTries

Problem statement

Build a class WordDictionary with two operations:

  • addWord(word) stores a lowercase word.
  • search(pattern) returns true if some stored word matches pattern. A pattern is made of lowercase letters and dots, where each . matches exactly one letter of any kind. The match covers the whole word, so the lengths must be equal.

It is a small version of wildcard lookup, like matching web-. against a set of hostnames.

Examples

Example 1

Input: addWord("web"), addWord("db"), addWord("dns"), search("d."), search("..."), search("w.b.")

Output: [true, true, false]

Explanation: d. matches db. ... matches web and dns. No stored word has four letters.

Example 2

Input: addWord("cache"), search("cach"), search("c.c.e")

Output: [false, true]

Explanation: Patterns must match the full word, so cach is not a hit.

Hints

Approach

Trie with a branching search. addWord is an ordinary trie insert that marks the last node as a word end.

search runs match(node, i):

  • If i equals the pattern length, the answer is whether node ends a word.
  • If pattern[i] is a letter, follow that single child (or fail if it's missing).
  • If it is ., try match(child, i + 1) for every child and succeed if any does.

Patterns without dots cost O(L), like a normal trie. Dots multiply the branches, so the worst case is 26^d paths for d dots, but the trie only has branches that real words created, which keeps typical queries far cheaper than scanning every word.

ComplexityTime addWord O(L), search O(L) without dots, O(26^d · L) worst caseSpace O(total characters added)
Python
class WordDictionary:
def __init__(self):
self.root = {}
def addWord(self, word):
node = self.root
for ch in word:
node = node.setdefault(ch, {})
node["$"] = True
def search(self, pattern):
def match(node, i):
if i == len(pattern):
return "$" in node
ch = pattern[i]
if ch == ".":
return any(match(child, i + 1) for key, child in node.items() if key != "$")
child = node.get(ch)
return child is not None and match(child, i + 1)
return match(self.root, 0)
d = WordDictionary()
for w in ["web", "db", "dns"]:
d.addWord(w)
print([d.search("d."), d.search("..."), d.search("w.b.")])
d = WordDictionary()
d.addWord("cache")
print([d.search("cach"), d.search("c.c.e")])

Follow-up questions

  • Support * meaning any run of letters, including none. How does the recursion change?
  • Add count(pattern) that returns how many stored words match.

Frequently asked questions

Wildcard matching over a set of names is routine infra work: host patterns in inventories, topic wildcards in message brokers, path patterns in routers. This problem is the gentlest version of it and tests whether you can extend a trie search with branching recursion without losing track of the index.

You could turn the pattern into a regex and test every word, but that is the brute force with extra overhead: it still scans the whole dictionary. The trie avoids looking at words whose prefixes already fail to match.

Keep a second index from word length to count (or to a set of words). A pattern that is only dots is then a single lookup. More generally, bucketing tries by word length removes every candidate with the wrong length up front.