String
Depth-First Search
Design
Trie
Design a data structure that supports adding new words and finding if a string matches any previously added string.
Implement the class:
- `addWord(word)` adds `word` to the data structure.
- `search(word)` returns `true` if there is any string in the data structure that matches `word` or `false` otherwise. `word` may contain dots `'.'` where dots can be matched with any letter.
In this harness, each test case adds a list of words and then performs a single `search` query, returning its boolean result.
Example 1
Input: addWord("bad"); addWord("dad"); addWord("mad"); search("pad")
Output: false
Example 2
Input: addWord("bad"); addWord("dad"); addWord("mad"); search("bad")
Output: true
Example 3
Input: addWord("bad"); addWord("dad"); addWord("mad"); search(".ad")
Output: true
Constraints
- •
1 <= word.length <= 25 - •
word in addWord consists of lowercase English letters. - •
word in search consists of '.' or lowercase English letters. - •
At most 2 dots are present in word for search queries.
Time Complexity
O(L) or O(26^L) with dots