Wildcard & Backtracking on Tries

Foundations

In the first lesson, every character of a query named exactly one edge to follow. Now, what if a query character can be anything, so several edges fit and you cannot know which one leads to a match?

Search recursively and backtrack. A call holds a node and a position in the pattern: a fixed letter follows its one edge or fails, while a wildcard tries each child in turn, and the first child whose subtree matches the rest of the pattern returns success. A failed child costs nothing more; the call backs up and tries the next. At the pattern's end, a call succeeds only on an isEnd node.

In the trie of words = ["to", "tea", "ten", "inn"], match t.n, where . matches any letter. Follow t; the dot then tries t's children. o has no child n, so that branch fails and the search backs up. e has one, and that n has isEnd set: ten matches. The i branch is never touched, because t was fixed.

Case Scenario

Design Add and Search Words stores words with addWord and asks search to match patterns where . stands for any letter. After adding bad, dad, and mad, search("pad") fails at the root, search("bad") follows one path, and search(".ad") and search("b..") let each dot branch over children until a marked node matches: False, True, True, True.

The direct approach compares the pattern with every stored word, letter by letter, treating . as a match. Each search costs O(n · L) for n words, and a pattern that matches nothing scans the whole dictionary, even though one mismatched fixed letter rules out every word below that edge.