## Algorithm

Problem Name: 211. 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:

• `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:

```Input
Output
[null,null,null,null,false,true,true,true]

Explanation
WordDictionary wordDictionary = new WordDictionary();
wordDictionary.search("b.."); // return True
```

Constraints:

• `1 <= word.length <= 25`
• `word` in `addWord` consists of lowercase English letters.
• `word` in `search` consist of `'.'` or lowercase English letters.
• There will be at most `3` dots in `word` for `search` queries.
• At most `104` calls will be made to `addWord` and `search`.

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
typedef struct dict_s {
int is_leaf;
struct dict_s *child[26];
} WordDictionary;
​
/** Initialize your data structure here. */
WordDictionary* wordDictionaryCreate() {
WordDictionary *obj;

obj  = calloc(1, sizeof(WordDictionary));
//assert(obj);

return obj;
}
​
/** Adds a word into the data structure. */
void wordDictionaryAddWord(WordDictionary* obj, char* word) {
int k;

if (!word || !*word) return;

while (*word) {
k = *word - 'a';
if (!obj->child[k]) {
obj->child[k] = calloc(1, sizeof(WordDictionary));
//assert(obj->child[k]);
}
obj = obj->child[k];
word ++;
}
obj->is_leaf = 1;
}
​
/** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */
bool wordDictionarySearch(WordDictionary* obj, char* word) {
int k;

while (obj && *word) {
if (*word == '.') {
for (k = 0; k  <  26; k ++) {
if (wordDictionarySearch(obj->child[k], word + 1)) {
return true;
}
}
return false;
} else {
k = *word - 'a';
obj = obj->child[k];
word ++;
}
}

return (obj && obj->is_leaf) ? true : false;
}
​
void wordDictionaryFree(WordDictionary* obj) {
int i;
for (i = 0; i  <  26; i ++) {
if (obj->child[i]) wordDictionaryFree(obj->child[i]);
}
free(obj);
}
``````
Copy The Code &

Input

cmd

Output

cmd
[null,null,null,null,false,true,true,true]

### #2 Code Example with C++ Programming

```Code - C++ Programming```

``````
class WordDictionary {
public:
WordDictionary() {}

words[word.size()].push_back(word);
}

bool search(string word) {
for(auto s: words[word.size()]) if(isEqual(s, word)) return true;
return false;
}

private:
unordered_map<int, vector < string>>words;

bool isEqual(string a, string b){
for(int i = 0; i  <  a.size(); i++){
if(b[i] == '.') continue;
if(a[i] != b[i]> return false;
}
return true;
}
};
``````
Copy The Code &

Input

cmd

Output

cmd
[null,null,null,null,false,true,true,true]

### #3 Code Example with Java Programming

```Code - Java Programming```

``````
class WordDictionary {

private Node root;

public WordDictionary() {
this.root = new Node();
}

Node curr = root;
for (char c : word.toCharArray()) {
if (curr.children[c - 'a'] == null) {
curr.children[c - 'a'] = new Node();
}
curr = curr.children[c - 'a'];
}
curr.isWord = true;
}

public boolean search(String word) {
Node curr = root;
return searchHelper(word, 0, curr);
}

private boolean searchHelper(String word, int idx, Node curr) {
if (idx == word.length()) {
return curr.isWord;
}
if (word.charAt(idx) != '.' && curr.children[word.charAt(idx) - 'a'] == null) {
return false;
}
if (word.charAt(idx) == '.') {
for (Node child : curr.children) {
if (child != null && searchHelper(word, idx + 1, child)) {
return true;
}
}
return false;
}
return searchHelper(word, idx + 1, curr.children[word.charAt(idx) - 'a']);
}

private static class Node {
Node[] children;
boolean isWord;

public Node() {
this.children = new Node[26];
this.isWord = false;
}
}
}
``````
Copy The Code &

Input

cmd

Output

cmd
[null,null,null,null,false,true,true,true]

### #4 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
class TrieNode {
constructor() {
this.children = [];
this.isWord = false;
}
}

const WordDictionary = function() {
this.root = new TrieNode();
this.aCode = "a".charCodeAt(0);
};

/**
* Adds a word into the data structure.
* @param {string} word
* @return {void}
*/
let node = this.root;
for (let c of word.split("")) {
let code = c.charCodeAt(0);
if (node.children[code - this.aCode] == null) {
node.children[code - this.aCode] = new TrieNode();
}
node = node.children[code - this.aCode];
}
node.isWord = true;
};

/**
* Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter.
* @param {string} word
* @return {boolean}
*/
WordDictionary.prototype.search = function(word) {
return this._match(word.split(""), 0, this.root);
};
WordDictionary.prototype._match = function(arr, k, node) {
if (k == arr.length) {
return node && node.isWord;
}
if (arr[k] === ".") {
for (let i = 0; node != null && i  <  node.children.length; i++) {
if (
node.children[i] !== null &&
this._match(arr, k + 1, node.children[i])
) {
return true;
}
}
} else {
return (
node != null && node.children[arr[k].charCodeAt(0) - this.aCode] != null &&
this._match(arr, k + 1, node.children[arr[k].charCodeAt(0) - this.aCode])
);
}
return false;
};
``````
Copy The Code &

Input

cmd

Output

cmd
[null,null,null,null,false,true,true,true]

### #5 Code Example with Python Programming

```Code - Python Programming```

``````
class TrieNode:
def __init__(self):
self.children = [None] * 26
self.last = False
class WordDictionary:

def __init__(self):
"""
"""
self.root = TrieNode()

"""
Adds a word into the data structure.
:type word: str
:rtype: void
"""
curr = self.root
for char in word:
if not curr.children[ord(char) - ord("a")]: curr.children[ord(char) - ord("a")] = TrieNode()
curr = curr.children[ord(char) - ord("a")]
curr.last = True
def search(self, word):
"""
Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter.
:type word: str
:rtype: bool
"""
words = [self.root]
for char in word:
if char == ".": words = [child for node in words for child in node.children if node and child]
else: words = [node.children[ord(char) - ord("a")] for node in words if node and node.children[ord(char) - ord("a")]]
if words and words[-1] == ".": return True
else: return any([node.last for node in words if node.last])
``````
Copy The Code &

Input

cmd

Output

cmd
[null,null,null,null,false,true,true,true]

### #6 Code Example with C# Programming

```Code - C# Programming```

``````
using System.Collections.Generic;

namespace LeetCode
{
{

/** Initialize your data structure here. */
{
root = new Trie();
}

/** Adds a word into the data structure. */
{
var current = root;
foreach (var ch in word)
{
if (!current.Children.ContainsKey(ch))
current = current.Children[ch];
}

current.Finished = true;
}

/** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */
public bool Search(string word)
{
return Search(word, root);
}

private bool Search(string word, Trie startPoint)
{
var current = startPoint;
for (int i = 0; i  <  word.Length; i++)
{
var ch = word[i];
if (ch == '.')
{
foreach (var key in current.Children.Keys)
{
if (Search(word.Substring(i + 1), current.Children[key]))
return true;
}
return false;
}
else if (current.Children.ContainsKey(ch))
current = current.Children[ch];
else
return false;
}

return current.Finished;
}

private class Trie
{
public Dictionary < char, Trie> Children = new Dictionary();
public bool Finished = false;
}
}
``````
Copy The Code &

Input

cmd