### Problem Statement

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

**Problem link**

### Video Tutorial

You can find the detailed video tutorial here### Thought Process

It's a string pattern searching problem, and because it matches the word strictly from the beginning to the end (note, even the partial matching is considered False, e.g., word "abcd", search("abc") should return False), the Trie (prefix tree) data structure comes very handy. It's a common simple data structure that often comes in coding interviews, be sure you can write it bug free.Once we are familiar with Trie,

*addWord*simply builds the Trie and

*search*just looks for the exact matching. One tricky part of this problem is ".", which can match any one and only one letter. This requires a recursive search of all the sub-nodes in the trie when encountering a "."

Even not asked in this leetcode question, but there are some very good follow up question

- If we support "*" matching, Similar to Leetcode wildcard matching, how would you solve it? Solution here
- How do you remove a word from the trie?

### Solutions

#### Time Complexity:

- addWord: O(N), N is the length of the word
- search: O(M), where M is the entire Trie's space (i.e., the total number of Trie nodes). Think about a worst case of N "............" dots. where N is the length of the word that is larger than the depth of the Trie (larger than the longest word seen so far). More specifically, it's N * (Nodes on Trie's each level) = N * (M / lgM) assuming trie's height is lgM, for worst case, N equals lgM, so N *(M / lgM) = lgM * (M / lgM) = M. Note a trie could be compressed (e.g., the single nodes are merged back to the upper level) but this analysis still holds true

- addWord: O(N), creating N more nodes in the trie, N is the length of the word
- search: No additional space needed

## No comments:

## Post a Comment