The problem
Design a structure with addWord(word), which stores a word, and search(word), which says whether any stored word matches. In a search, the character . matches any one letter.
Examples
01
- Input
["WordDictionary", "addWord", "addWord", "addWord", "search", "search", "search", "search"] [[], ["bad"], ["dad"], ["mad"], ["pad"], ["bad"], [".ad"], ["b.."]]
- Output
[null, null, null, null, false, true, true, true]
Constraints
- 1 ≤ word.length ≤ 25
- Stored words are lowercase letters; searches may also contain
. - At most 2 dots in each search.
- At most 10⁴ calls in total.
The idea
Store the words in a trie. A search with ordinary letters walks one path, as in Implement Trie.
A . can be any letter, so at that point the search branches: it tries every child, and succeeds if any of them leads on to a match. This is depth-first search — following one choice all the way before trying the next. With at most two dots, a search visits at most 26 × 26 paths.
- Time
- O(L) to add; O(26ᵈ × L) to search with d dots
- Space
- O(total letters stored)
Solution · every language run against every case
class WordDictionary: def __init__(self): self.root = {} # a trie: letter -> child node; "$" marks the end of a word def addWord(self, word: str) -> None: node = self.root for c in word: node = node.setdefault(c, {}) node["$"] = True def search(self, word: str) -> bool: def find(node, i): if i == len(word): return "$" in node if word[i] == ".": # any letter: try every child return any(find(child, i + 1) for c, child in node.items() if c != "$") return word[i] in node and find(node[word[i]], i + 1) return find(self.root, 0)