Design Add and Search Words Data Structure
Design a data structure that supports adding new words and finding if a string matches any previously added string. Implement the WordDictionary class with addWord(word) and search(word) methods. 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.

30:00

Design Add and Search Words Data Structure
medium
Topics
Companies

Design a data structure that supports adding new words and finding if a string matches any previously added string. Implement the WordDictionary class with addWord(word) and search(word) methods. 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 1:
Input: {"commands":["WordDictionary","addWord","addWord","addWord","search","search","search","search"],"values":[[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]}
Output: [null,null,null,null,false,true,true,true]
Constraints:

  • 1≤word.length≤251 \leq \text{word.length} \leq 25

  • word in addWord consists of lowercase English letters.

  • word in search consists of . or lowercase English letters.

  • There will be at most 22 dots in word for search queries.

  • At most 10410^4 calls will be made to addWord and search.

Input
arr ={"commands":["WordDictionary","addWord","addWord","addWord","search","search","search","search"],"values":[[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]}

Initialize WordDictionary with Trie structure

root

Operations

Word end

Search path

.

Wildcard (any char)

Variables
No variables to display
DepthFunction Call
Stack empty
0/8