LeetCode #211 Add and Search Word — Data structure design

Medium

Problem

Design a data structure that supports the following two operations:

void addWord(word)
bool search(word)

search(word) can search a literal word or a regular expression string containing only letters a-z or .. A . means it can represent any one letter.

Example:

addWord("bad")
addWord("dad")
addWord("mad")
search("pad") -> false
search("bad") -> true
search(".ad") -> true
search("b..") -> true

Note:
You may assume that all words are consist of lowercase letters a-z.

Solution

It’s trivial that we should use a trie to save added words. However, we should search all children once we meet a . in search operation.

Complexity

It’s trivial that addWord takes O(k) time if k denotes to the length of given word.

For search, although we do recursion whenever we meet ., the deep of calling stack will only be at most k. Hence, it’s time complexity is O(k) as well.