Add and Search Word – Data structure design LeetCode

The problem “Add and Search Word – Data structure design LeetCode” asks us to create or design a new data structure. Such that which can be used for adding or storing a word and searching the words where the search function can search even a regular expression from the word.

For instance :

If string/word = “hey” is stored in the map then the following functions will give the same output –

1. search (..y).

2. search (.e.).

3. search (h..).

All the above three function calls will result in the output to be true.

Example

addword ("code")
addword ("java")
addword ("when")
search ("blue")
search ("java")
search ("co..")

False
True
True

addword ("who")
addword ("why")
search ("why")
search ("hey")
search ("the")

True
False
False

Using Resizable array and Hashmap

Algorithm

1. Initialize a class for the new data structure.
2. After that, initialize a resizable array of string type and a hashmap of the type of the pair of the string and the integer type.
3. Create a function to add the word in the new data structure which accepts a string variable as its parameter.
4. After that, check if the given string is already present in the map, return.
5. Else insert the given string at the last index of the array and in the map also.
6. Similarly, create another function to search the word in the new data structure which accepts a string variable as its parameter.
7. Search the given string variable on the map.
8. If the string variable is present in the map print “True”.
9. Else check the regular expression. If it is found print “True”.
10. Print “False”.

Implementation

C++ code for Add and Search Word – Data structure design LeetCode

#include<bits/stdc++.h> 
using namespace std; 
  
class newStructure{ 
    vector <string> arr; 
      
    map <string, int> Map; 
  
    public: 
        void addword(string x){ 
            
            if(Map.find(x) != Map.end()) 
                return; 
                  
            int index = arr.size(); 
            arr.push_back(x); 
                  
            Map.insert(std::pair<string,int>(x, index)); 
        } 
              
              
        void search(string x){ 
            if(Map.find(x) != Map.end()){ 
                cout<<"True"<<endl;
                return;
            }    
            else{
                regex b(x);
                for(int i=0; i<arr.size(); i++){
                    if(regex_match(arr[i],b)){
                        cout<<"True"<<endl;
                        return;
                    }
                }
            }    
            cout<<"False"<<endl;
        } 
}; 
  
int main(){ 
    newStructure ds;
    
    ds.addword("code"); 
    ds.addword("java"); 
    ds.addword("when"); 
    
    ds.search("blue");
    ds.search("java");
    ds.search("co..");
    
    return 0;
}

False
True
True

Java code for Add and Search Word – Data structure design LeetCode

import java.util.*; 
import java.util.regex.Pattern;

class newStructure{ 
    ArrayList<String> arr; 
    HashMap<String, Integer>  map; 
    
    public newStructure(){ 
        arr = new ArrayList<String>(); 
        map = new HashMap<String, Integer>(); 
    } 
    
    void addword(String x){ 
        if(map.get(x) != null) 
            return; 
        
        int s = arr.size(); 
        arr.add(x); 
        map.put(x, s); 
    } 
    
    void search(String x){ 
        if(map.get(x)!=null){
            System.out.println("True");
            return;
        } 
        else{
            Pattern regex = Pattern.compile(x);
            
            for(String s:arr){
                if(regex.matcher(s).matches()){
                    System.out.println("True");
                    return;
                }
            }
        }
        System.out.println("False");
    } 
} 

class Main{ 
    public static void main (String[] args){ 
        newStructure ds = new newStructure();
        
        ds.addword("code"); 
        ds.addword("java"); 
        ds.addword("when"); 
        
        ds.search("blue"); 
        ds.search("java"); 
        ds.search("co.."); 
        
    } 
}

False
True
True

Complexity Analysis for Add and Search Word – Data structure design LeetCode

Time Complexity

O(n*m) where n is the number of words added and m is the length of the words to be searched.

Space Complexity

O(n) because this program uses space for n elements in the resizable array and hashmap, therefore the space complexity is O(n).

References