Design Add and Search Words Data Structure
Medium · Tries · String · Depth-First Search · Design · Trie
Problem
Design a dictionary that stores words and answers lookups in which some letters may be wildcards. Implement the WordDictionary class:
- WordDictionary() creates an empty dictionary.
- addWord(word) adds word to the dictionary.
- search(word) returns True if some stored word matches word, and False otherwise. The query may contain . characters, and each . matches any single letter. A match must have exactly the same length as the query.
Tests replay a call sequence: the first entry names the class, each later entry is a method with its arguments, and calls returning nothing report None.
Examples
Input: addWord("bad"), addWord("dad"), addWord("mad"), search("pad"), search("bad"), search(".ad"), search("b..")
Output: False, True, True, then True"pad" was never added. ".ad" matches bad, dad and mad, and "b.." matches bad.
Input: addWord("at"), search("a"), search("a."), search(".t")
Output: False, True, then True"a" is only the start of a stored word, so it does not match. Each dot stands for exactly one letter.
Constraints
- 1 <= len(word) <= 25
- addWord gets lowercase English letters only
- search gets lowercase letters and '.', with at most 2 dots
- Up to 10^4 calls to addWord and search in total
Approaches
- Words grouped by length, scanned — time O(1) add, O(k · L) search, space O(total characters)
Follow-up
With at most two dots, a search visits at most 26² paths. What if the number of dots were unlimited? Could you speed up queries that start with dots, such as "..ad", by also storing each word reversed, or by grouping words by length?
Related problems
Start free on Cariara · Coding problems · System design studio
