# Design Add and Search Words Data Structure LeetCode Solution

Difficulty Level Medium
Depth First Search Design String TrieViews 867

## Problem Statement:

Design Add and Search Words Data Structure LeetCode Solution says – 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

["WordDictionary","addWord","addWord","addWord","search","search","search","search"]


Output

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



Explanation

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

## Approach for Design Add and Search Words Data Structure Leetcode Solution:

### Idea:

• We generally consider Trie data structure to solve problems efficiently which involves operations like string matching. If you are new to Trie then first understand what is Trie and how it is implemented, and how searching is done it.
• You can refer to Trie
• Coming on to the solution. First, we will create a Trie Node consisting of 26 child nodes, one for each character of the lowercase English letters, and will declare a head node, denoting the root node of the Trie. The Node structure will also consist of a flag named isEnd which will mark the end of a word if set to true.
• addWord(): This function simply involves the insertion of a word in a Trie. We will iterate over all the words and will insert them one by one in the Trie.
• search(): For the word which does not involve any “.” in them, the search is simple we just need to iterate over the Trie and check if the particular word exists in the Trie or not.
• The tricky part is when “.” is present in the word. Here we need to keep in mind that as soon as we see a “.” we can use any of the characters from the lower case English alphabet, to form a word that is present in the Trie. So the idea is to search for all the possibilities in the Trie for that particular node i.e., we need to explore all possible paths at each . level.

## Code:

### Design Add and Search Words Data Structure Leetcode C++ Solution:

class WordDictionary {
public:
struct Node{
Node* child[26]={NULL};
bool isEnd=false;
};

WordDictionary() {
}

for(auto it:word){
if(!ptr->child[it-'a'])
ptr->child[it-'a'] = new Node();
ptr = ptr->child[it-'a'];
}
ptr->isEnd = true;
}

bool searchHelper(Node* node,string s){
Node* ptr = node;
int pos=0;
for(auto it:s){
if(it=='.'){
for(int i=0;i<26;i++){
if(ptr->child[i]){
if(searchHelper(ptr->child[i],s.substr(pos+1)))
return true;
}
}
return false;
}
else if(ptr->child[it-'a']){
ptr = ptr->child[it-'a'];
}
else
return false;
pos++;
}
return ptr->isEnd;
}

bool search(string word) {
}
};

### Design Add and Search Words Data Structure Leetcode Python Solution:

class Node:
def __init__(self):
self.child = {}
self.isEnd = False

class WordDictionary:

def __init__(self):

def addWord(self, word: str) -> None:
for it in word:
if it not in ptr.child:
ptr.child[it] = Node()
ptr = ptr.child[it]
ptr.isEnd = True
def search(self, word: str) -> bool:
def searchHelper(node,s):
ptr = node
pos=0
for it in s:
if it==".":
for i in ptr.child:
if searchHelper(ptr.child[i],s[pos+1:]):
return True
return False
elif it in ptr.child:
ptr = ptr.child[it]
else:
return False
pos+=1
return ptr.isEnd

return searchHelper(self.head,word)

## Complexity Analysis:

• Time Complexity: The time complexity of the above code is for the words without dots, where “m” is the key length, and O(N.26^ M) for the words without dots, where n is the number of keys.
• Space Complexity: The space complexity of the above code is  for the search of words without dots, and O(m) for the words with dots, in order to keep the recursion stack.

Related Problem: Implement Trie (Prefix Tree) Leetcode Solution

Translate »