Word Dictionary with Wildcards | Practice

Write a class WordDictionary that stores lowercase words and finds them by pattern:

WordDictionary() makes an empty dictionary.
addWord(word) stores word.
search(word) returns true if some stored word matches word, and false otherwise. Here word may contain dots: each . matches any one letter, and every other letter must match itself. A match has exactly the same length.

Each test is a list of calls, starting with the constructor; the expected answer lists what each call returns (null for the constructor and for addWord).

Example 1

Calls: WordDictionary(), addWord("cat"), addWord("cart"), search("c.t"), search("c..t"), search("ca")
Returns: [null, null, null, true, true, false]

c.t matches "cat" and c..t matches "cart", but nothing matches ca: a match must have the same length.

Example 2

Calls: WordDictionary(), addWord("dog"), search(".o."), search("d.gs"), search(".")
Returns: [null, null, true, false, false]

Constraints

Stored words have 1 to 25 lowercase English letters.
Searched words have 1 to 25 characters, each a lowercase letter or ., with at most 2 dots.
A test makes at most 10⁴ calls.

Show the pattern

Trie, Backtracking

The stored words share starts, so a trie holds them. A `.` could be any letter, so there the search tries each child in turn and backs up when a branch fails.

See trie in a visualiser

Show the approach

Store the words in a trie: each node maps letters to child nodes and has a flag end for a word ending there. addWord walks down from the root, making missing children, and sets end on the last node.

search is a depth-first search of the trie, steered by the pattern. match(node, i) asks whether the pattern from position i onwards can be matched starting from node:

at the end of the pattern, the answer is node.end;
for a letter, follow that letter's child, or fail if there isn't one;
for a ., try every child, and succeed as soon as one of them does. A branch that fails just returns, and the next child is tried.

Time: O(L) to add; O(L) to search without dots, up to O(26ᵈ · L) with d dots · Space: O(total letters stored)

Brush up firstTrie (Prefix Matching) visualiser