Design Add and Search Words Data Structure LeetCode Solution

Table of Contents

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"]
[[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]

Output

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

Explanation

WordDictionary wordDictionary = new WordDictionary();
wordDictionary.addWord("bad");
wordDictionary.addWord("dad");
wordDictionary.addWord("mad");
wordDictionary.search("pad");  // return False
wordDictionary.search("bad"); // return True
wordDictionary.search(".ad"); // return True
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;
    };
    
    Node* head = NULL;
   
    WordDictionary() {
        head = new Node();
    }
    
    void addWord(string word) {
        Node* ptr = head;
        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) {
        return searchHelper(head,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):
        self.head = Node()
    
    def addWord(self, word: str) -> None:
        ptr = self.head
        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 $O (m)$ 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 $O (1)$ 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