[LeetCode] 211. Add and Search Word - Data Structure Design

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.

For 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.

click to show hint.

You should be familiar with how a Trie works. If not, please work on this problem: Implement Trie (Prefix Tree) first.

Thought process:

Use trie.

1. addWord: iterate through the word. Start from the root trie node. If current character does not map to a trie node, create a new one and map them. Otherwise, go to the next trie node.
2. Search: iterate through the word. If current character is '.', then iterate through the entire map and recursively search for the remaining string. Otherwise, move current trie node to the child and check if the last node is word.

Solution:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64

class WordDictionary { class TrieNode { TrieNode[] children; boolean isWord; TrieNode() { children = new TrieNode[26]; } } private TrieNode root; /** Initialize your data structure here. */ public WordDictionary() { root = new TrieNode(); } /** Adds a word into the data structure. */ public void addWord(String word) { TrieNode current = root; for (char c : word.toCharArray()) { int index = c - 'a'; if (current.children[index] == null) { current.children[index] = new TrieNode(); } current = current.children[index]; } current.isWord = true; } /** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */ public boolean search(String word) { return search(word, 0, root); } private boolean search(String word, int index, TrieNode node) { if (index == word.length()) { return node.isWord; } char c = word.charAt(index); if (c == '.') { for (TrieNode child : node.children) { if (child != null && search(word, index + 1, child)) { return true; } } return false; } else { TrieNode child = node.children[c - 'a']; if (child == null) { return false; } return search(word, index + 1, child); } } } /** * Your WordDictionary object will be instantiated and called as such: * WordDictionary obj = new WordDictionary(); * obj.addWord(word); * boolean param_2 = obj.search(word); */

Time complexity:
Say the length of word is n.

1. addWord: O(n).
2. search: in the worst case, the word is comprised of '.', and all characters in a trie node is mapped to a child. Then search will go through every possible path from root to leaf. The overall time complexity is O(26^n).