Add and Search Word – Data Structure Design ❤️

Design a data structure GFGDictionary that enables to support the feature of adding new words and searching for words. The GFGDictionary class should have the following implementation:

GFGDictionary(): constructor to initialize the object
void insertWord(word): function to insert word into the data structure.
bool findWord(word): function to return true if word is present in the data structure, else return false. The word may contain dots ‘.’ which can be matched with any letter.

Examples:

Input: function calls = {“GFGDictionary”, “insertWord”, “insertWord”, “insertWord”, “findWord”, “findWord”, “findWord”, “findWord”}, strs = {{}, {“bad”}, {“dad”}, {“mad”}, {“pad”} ,{“bad”}, {“.ad”}, {“b..”}}
Output: {null, null, null, null, false, true, true, true}
Explanation: Firstly, GFGDictionary constructor is called. Then “bad”, “dad” and “mad” are inserted into the dictionary. So the first four values are null. Now, for the remaining findWord operations:

Since, “pad” is not present in GFGDicitonary, therefore return false.
Since, “bad” is present in GFGDicitonary, therefore return true.
Since, “.ad” can be matched with “bad” and “bad” is present in GFGDicitonary, therefore return true.
Since, “b..” can be matched with “bad” and “bad” is present in GFGDicitonary, therefore return true.
Input: function calls = {“GFGDictionary”, “insertWord”, “insertWord”, “findWord”, “findWord”}, strs = {{}, {“geek”}, {“gfg”}, {“g.g”}, {“.g.”}}
Output: {null, null, null, true, false}
Explanation: Firstly, GFGDictionary constructor is called. Then “geek” and “gfg” are inserted into the dictionary. So the first three values are null. Now, for the remaining findWord operations:

Since, “g.g” can be matched with “gfg” and “gfg” is present in GFGDicitonary, therefore return true.
Since, “.g.” cannot be matched with any string in GFGDicitonary, therefore return false.

Approach: To solve the problem, follow the below idea:

To efficiently support the ‘insertWord’ and ‘findWord’ operations, implementation of Trie data structure is required. For inserting a word, we can simply insert the word in the trie. And while searching, we can start from the root of the trie and match character by character as we move down in the trie. At any point while matching, if we encounter a ‘.’, then we need to move to all the child nodes of the current node.

Step-by-step algorithm:

Create a class TrieNode to implement a node of Trie data structure.
Create a class GFGDictionary with a constructor to initialize the root node of the trie data structure.
Define the function insertWord(word):
- Start traversing the trie from the root node, according to the characters in the word.
- If there is no Trienode corresponding to the current character, then create a TrieNode and move to that node.
- After traversing over all the characters, mark the current node as end of the word.
Define the function findWord(word):
- Start traversing the trie from the root node, according to the characters in the word.
- If the current character is a dot ‘.’, then move to all the trienodes available at the current node.
- Else If there is no Trienode corresponding to the current character, return false.
- If all the characters are traversed, check if the current node is the end of any word. If yes, return true otherwise return false.

Below is the implementation of the algorithm:

Python

# Class to implement a node of Trie data structure
class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end_of_word = False


# GFGDictionary class
class GFGDictionary:

      # constructor
    def __init__(self):
        self.root = TrieNode()

    # function to insert word to the data structure
    def insertWord(self, word: str) -> None:
        current = self.root
        for char in word:
            if char not in current.children:
                current.children[char] = TrieNode()
            current = current.children[char]
        current.is_end_of_word = True

    # function to find the word in GFGDictionary
    def findWord(self, word: str) -> bool:
        def dfs(node, i):
            if i == len(word):
                return node.is_end_of_word
            
            if word[i] == '.':
                for child in node.children.values():
                    if dfs(child, i + 1):
                        return True
            elif word[i] in node.children:
                return dfs(node.children[word[i]], i + 1)
            
            return False
        
        return dfs(self.root, 0)

# Sample Input
gfgDict = GFGDictionary()
gfgDict.insertWord("bad")
gfgDict.insertWord("dad")
gfgDict.insertWord("mad")
print(gfgDict.findWord("pad"))  
print(gfgDict.findWord("bad"))  
print(gfgDict.findWord(".ad"))  
print(gfgDict.findWord("b.."))

Output

False
True
True
True

Time Complexity: O(M * (26 ^ N)), where M is the number of words to be searched, and N is the length of the word.
Auxiliary Space: O(M)

Add and Search Word – Data Structure Design

Contact Us