DSA Adding and Searching Words with Wildcards

The problem

Adding and searching words with wildcards means building one class with two operations. Add_word stores a word. Search answers whether a stored word matches a pattern.

A pattern holds letters and dots. A dot is a wildcard, a symbol that matches any one letter. A dot matches exactly one letter, never zero and never two.

adds = ["bad", "dad", "mad", "bed"]
checks = [
    ("bad", True),
    ("pad", False),
    (".ad", True),
    ("..d", True),
    ("b.d", True),
    ("b.z", False),
    ("....", False),
]
for word in adds:
    print("add", word)
for pattern, expected in checks:
    print("search", pattern, "->", expected)

The plain patterns test exact spelling. The dot patterns test branching. The last pattern fails on length alone, because no stored word has four letters.

Intuition: a plain trie search breaks on a dot

A trie is the natural store for words, and a plain trie search follows one child per letter. That search has no move to make at a dot. No child is named with a dot character.

The failure is silent, which makes it dangerous. The search answers False for a pattern that should match, and nothing in the answer says why.

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

root = TrieNode()
for word in ["bad", "dad", "mad"]:
    node = root
    for letter in word:
        if letter not in node.children:
            node.children[letter] = TrieNode()
        node = node.children[letter]
    node.is_end = True

def search_exact(node, pattern):
    for letter in pattern:
        if letter not in node.children:
            return False
        node = node.children[letter]
    return node.is_end

print("root children:", sorted(root.children))
print("dot among children:", "." in root.children)
print("search bad:", search_exact(root, "bad"))
print("search .ad:", search_exact(root, ".ad"))

The stored word bad matches the pattern .ad letter by letter under the wildcard rule. The exact-only search still answers False. The dot needs a different move, and that move is branching.

Brute force: keep a list, match the pattern against every word

The naive design stores words in a list. A search walks the list and tests the pattern against each word. A word matches when its length equals the pattern length and every pattern letter is a dot or equals the word letter.

The design handles dots correctly. Its cost is the scan. A failed search pays for every stored word, and a successful one pays until the match.

def matches(pattern, word, counter):
    if len(pattern) != len(word):
        return False
    for p, w in zip(pattern, word):
        counter[0] += 1
        if p != "." and p != w:
            return False
    return True

class ListWords:
    def __init__(self):
        self.words = []
        self.comparisons = 0

    def add_word(self, word):
        self.words.append(word)

    def search(self, pattern):
        counter = [0]
        for word in self.words:
            if matches(pattern, word, counter):
                self.comparisons += counter[0]
                return True
        self.comparisons += counter[0]
        return False

d = ListWords()
for word in ["bad", "dad", "mad", "bed"]:
    d.add_word(word)
for pattern in ["bad", "pad", ".ad", "...."]:
    before = d.comparisons
    print("search", pattern, ":", d.search(pattern), "- letter comparisons:", d.comparisons - before)

The failing pattern pad spends a comparison on each stored word before giving up. The length check saves the four-dot pattern from letter work, but it still inspects every word. Nothing is shared between the stored words, so nothing is saved between searches.

The optimal solution: branch at every dot

The state is a trie of the stored words, and the search is a walk that branches at a dot. A plain letter follows its one child. A dot tries every child of the current node, and one branch reaching a word end with the pattern spent makes the whole search True.

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


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

    def add_word(self, word):
        node = self.root
        for letter in word:
            if letter not in node.children:
                node.children[letter] = TrieNode()
            node = node.children[letter]
        node.is_end = True

    def search_from(self, node, pattern, index, visited):
        visited[0] += 1
        if index == len(pattern):
            return node.is_end
        letter = pattern[index]
        if letter == ".":
            found = False
            for child in node.children.values():
                if self.search_from(child, pattern, index + 1, visited):
                    found = True
            return found
        if letter not in node.children:
            return False
        return self.search_from(node.children[letter], pattern, index + 1, visited)

    def search(self, pattern):
        visited = [0]
        found = self.search_from(self.root, pattern, 0, visited)
        return found, visited[0]

words = WordDictionary()
for word in ["bad", "dad", "mad", "bed"]:
    words.add_word(word)
checks = [
    ("bad", True),
    ("pad", False),
    (".ad", True),
    ("..d", True),
    ("b.d", True),
    ("b.z", False),
    ("....", False),
]
passed = 0
for pattern, expected in checks:
    found, visited = words.search(pattern)
    ok = found == expected
    passed += 1 if ok else 0
    print("search", pattern, ":", found, "- nodes visited", visited, "- pass", ok)
print("Passed", passed, "of", len(checks))

All seven checks from the start of the article pass. The visited counts separate the two kinds of pattern. Exact patterns stay on one path, while dot patterns pay for the branches they open.

Walkthrough: searching for .ad

The walk starts at the root with the full pattern ahead of it. The first symbol is a dot, so the walk tries the root children in turn. The trace follows the first branch, which succeeds.

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

root = TrieNode()
for word in ["bad", "dad", "mad", "bed"]:
    node = root
    for letter in word:
        if letter not in node.children:
            node.children[letter] = TrieNode()
        node = node.children[letter]
    node.is_end = True

def trace(node, pattern, path):
    if not pattern:
        print("pattern spent at path", repr(path), "- word end:", node.is_end)
        return node.is_end
    letter = pattern[0]
    if letter == ".":
        for key in sorted(node.children):
            print("dot at path", repr(path), "tries child", key)
            if trace(node.children[key], pattern[1:], path + key):
                return True
        return False
    if letter not in node.children:
        print("letter", letter, "missing at path", repr(path))
        return False
    print("letter", letter, "at path", repr(path), "follows its child")
    return trace(node.children[letter], pattern[1:], path + letter)

print("result:", trace(root, ".ad", ""))

The dot tries child b first, and that branch spells bad. The letters a and d then follow single children, and the pattern ends exactly on a word end. Branches d and m stay unexplored in this trace, because one success settles the answer.

Complexity

An exact search visits one node per pattern letter, plus the final node, so its time is proportional to the pattern length. A dot pattern can branch at every level, so its worst case visits every node in the trie.

The trie stores one node per distinct letter position across the stored words. That node count is also the ceiling on a single search.

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


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

    def add_word(self, word):
        node = self.root
        for letter in word:
            if letter not in node.children:
                node.children[letter] = TrieNode()
            node = node.children[letter]
        node.is_end = True

    def search_from(self, node, pattern, index, visited):
        visited[0] += 1
        if index == len(pattern):
            return node.is_end
        letter = pattern[index]
        if letter == ".":
            found = False
            for child in node.children.values():
                if self.search_from(child, pattern, index + 1, visited):
                    found = True
            return found
        if letter not in node.children:
            return False
        return self.search_from(node.children[letter], pattern, index + 1, visited)

    def search(self, pattern):
        visited = [0]
        found = self.search_from(self.root, pattern, 0, visited)
        return found, visited[0]

def count_nodes(node):
    total = 1
    for child in node.children.values():
        total += count_nodes(child)
    return total

for extra in [[], ["sad"], ["sad", "tad"]]:
    words = WordDictionary()
    for word in ["bad", "dad", "mad", "bed"] + extra:
        words.add_word(word)
    found, visited = words.search("....")
    print("stored words", 4 + len(extra), "- trie nodes", count_nodes(words.root), "- worst search visits", visited)

The four-dot pattern matches nothing, so its search is forced to explore the whole tree. Its visited count equals the node count at each size. Growth in the dictionary is growth in the worst search, but exact searches never pay it.

Edge cases and pitfalls

A search on an empty dictionary answers False for every pattern. The root has no children, so plain letters miss and dots find no branch to try.

The empty pattern is spent at the root. It answers True only when an empty word was added, which sets the root end flag. Forgetting that the root can be a word end is the classic pitfall in this design.

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


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

    def add_word(self, word):
        node = self.root
        for letter in word:
            if letter not in node.children:
                node.children[letter] = TrieNode()
            node = node.children[letter]
        node.is_end = True

    def search_from(self, node, pattern, index, visited):
        visited[0] += 1
        if index == len(pattern):
            return node.is_end
        letter = pattern[index]
        if letter == ".":
            found = False
            for child in node.children.values():
                if self.search_from(child, pattern, index + 1, visited):
                    found = True
            return found
        if letter not in node.children:
            return False
        return self.search_from(node.children[letter], pattern, index + 1, visited)

    def search(self, pattern):
        visited = [0]
        found = self.search_from(self.root, pattern, 0, visited)
        return found, visited[0]

words = WordDictionary()
print("search bad, empty dictionary:", words.search("bad")[0])
print("search dot, empty dictionary:", words.search(".")[0])
words.add_word("a")
print("search dot, one-letter word stored:", words.search(".")[0])
print("search empty pattern:", words.search("")[0])
words.add_word("")
print("search empty pattern after adding an empty word:", words.search("")[0])
words.add_word("bad")
words.add_word("bad")
print("search bad after a duplicate add:", words.search("bad")[0])

The duplicate add changes no answer. The path for bad already exists, and setting its end flag again is harmless. Storage stays one path per distinct word.