# Leetcode 211 - Design add and search words data structure

`Note:`

`Trie`

- Check if a string exsits in a data structure,
`Trie`

is the way to go. But we only need to implement`insert`

for`trie`

cause we need to implement another`DFS`

search. - For searching, we need
`DFS`

as essentially`trie`

is a tree,.- Param: we need to know current
`trie`

node and current`word[i]`

of word. so`dfs(node, i)`

- Base: When
`i === word.length`

, we need to check if`node.isEnd`

is true. Otherwise it might not be true such as we search`app`

toward`apple`

. - When
`word[i]`

is`.`

, we need to iterate on every letter of`trie`

. In binary tree, we might do`return dfs(left) || dfs(right)`

, but here its a n-ary tree. The techinique is to write`if (dfs(nextNode, i+1)) return true`

. - When
`word[i]`

is not`.`

, if`word[i]`

is not presented in`node`

, just return false. Otherwise, we need to keep doing dfs on next node and increase i by 1.`return dfs(node[word[i]], i+1)`

- Param: we need to know current

- Check if a string exsits in a data structure,
`Regex`

- Know how to replace
`.`

with`[a-z]`

`word.replace(/\./g, '[a-z]')`

- Know how to build regex with strings using
`new Regex()`

. - Know
`search(regex)`

returns`-1`

if there is no match.

- Know how to replace

`Question:`

Design a data structure that supports adding new words and finding if a string matches any previously added string.

Implement the WordDictionary class:

`WordDictionary()`

Initializes the object.`void addWord(word)`

Adds word to the data structure, it can be matched later.`bool search(word)`

Returns true if there is any string in the data structure that matches word or false otherwise. word may contain dots ‘.’ where dots can be matched with any letter.

`Example:`

1 | Input: |

`Code:`

`Trie`

1 | var WordDictionary = function () { |

`Regex`

1 | var WordDictionary = function () { |