211. Add and Search Word - Data structure design
https://leetcode.com/problems/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.
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
You may assume that all words are consist of lowercase letters
a-z.
---
Intuition
Build a trie to store words, mark word with boolean, not string since exact match will not be useful with wildcard .
Use Hash Map / array of length 26 for storing children, keeps code clean and readable
Build the trie iteratively, check if current character exists, if not create it. set current to child node.. iterate
Search - recursion
Base case - if index == word.length() -- return current.isWord
if char == . recurse on all children with next index on search word, if any child is true, return true
if char == alphabet, check if child for that alphabet exists, and recurse on next index
---
Intuition
Build a trie to store words, mark word with boolean, not string since exact match will not be useful with wildcard .
Use Hash Map / array of length 26 for storing children, keeps code clean and readable
Build the trie iteratively, check if current character exists, if not create it. set current to child node.. iterate
Search - recursion
Base case - if index == word.length() -- return current.isWord
if char == . recurse on all children with next index on search word, if any child is true, return true
if char == alphabet, check if child for that alphabet exists, and recurse on next index
---
Related problems
---
208-implement-trie-prefix-tree
---
