વર્ડ ઉમેરો અને શોધો - ડેટા સ્ટ્રક્ચર ડિઝાઇન લેટકોડ


મુશ્કેલી સ્તર મધ્યમ
બેકટ્રેકીંગ ડિઝાઇન શબ્દમાળા ટ્રિ

સમસ્યા "વર્ડ ઉમેરો અને શોધો - ડેટા સ્ટ્રક્ચર ડિઝાઇન લેટકોડ" અમને નવું બનાવવા અથવા ડિઝાઇન કરવાનું કહે છે માહિતી માળખું. આવા કે જે કોઈ શબ્દ ઉમેરવા અથવા સ્ટોર કરવા અને શબ્દો શોધવા માટે વાપરી શકાય છે જ્યાં શોધ ફંક્શન શબ્દમાંથી નિયમિત અભિવ્યક્તિ પણ શોધી શકે છે.

દાખલા તરીકે :

જો શબ્દમાળા / શબ્દ = "હે" નકશામાં સંગ્રહિત છે, તો નીચેના કાર્યો સમાન આઉટપુટ આપશે -

1. શોધ (..ય).

2. શોધ (.ઇ.).

3. શોધ (ક ..).

ઉપરોક્ત ત્રણેય કાર્ય ક callsલ્સના પરિણામ રૂપે આઉટપુટ સાચા થશે.

વર્ડ ઉમેરો અને શોધો - ડેટા સ્ટ્રક્ચર ડિઝાઇન લેટકોડ

ઉદાહરણ

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

રેઝિઝેબલ એરે અને હેશમેપનો ઉપયોગ કરીને

અલ્ગોરિધમ

  1. નવા ડેટા સ્ટ્રક્ચર માટે વર્ગ શરૂ કરો.
  2. તે પછી, એક કદ બદલીને શરૂ કરો એરે શબ્દમાળા પ્રકાર અને એ હેશમેપ શબ્દમાળાની જોડીનો પ્રકાર અને પૂર્ણાંક પ્રકાર.
  3. નવા ડેટા સ્ટ્રક્ચરમાં શબ્દ ઉમેરવા માટે એક ફંક્શન બનાવો જે સ્વીકારે છે a શબ્દમાળા તેના પરિમાણ તરીકે ચલ.
  4. તે પછી, તપાસો કે આપેલ શબ્દમાળા નકશામાં પહેલેથી હાજર છે કે નહીં, પાછા ફરો.
  5. બાકી એરેના છેલ્લા ઇન્ડેક્સ પર આપેલ શબ્દમાળા દાખલ કરો અને નકશામાં પણ.
  6. એ જ રીતે, નવા ડેટા સ્ટ્રક્ચરમાં શબ્દ શોધવા માટે બીજું ફંક્શન બનાવો જે શબ્દમાળા વેરિયેબલને તેના પરિમાણ તરીકે સ્વીકારે છે.
  7. નકશા પર આપેલ શબ્દમાળા ચલ શોધો.
  8. જો શબ્દમાળા ચલ નકશા પ્રિન્ટ "ટ્રુ" માં હાજર છે.
  9. બાકી નિયમિત અભિવ્યક્તિ તપાસો. જો તે "ટ્રુ" છાપો.
  10. “ખોટી” છાપો.

અમલીકરણ

વર્ડ ઉમેરો અને શોધો માટે સી ++ કોડ - ડેટા સ્ટ્રક્ચર ડિઝાઇન લેટકોડ

#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

વર્ડ Addડ અને સર્ચ માટે જાવા કોડ - ડેટા સ્ટ્રક્ચર ડિઝાઇન લેટકોડ

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

વર્ડ એડ અને સર્ચ માટે જટિલતા વિશ્લેષણ - ડેટા સ્ટ્રક્ચર ડિઝાઇન લેટકોડ

સમય જટિલતા

ઓ (એન * મી) જ્યાં n એ શબ્દોની સંખ્યા ઉમેરવામાં આવે છે અને એમ શબ્દોની શોધની લંબાઈ છે.

અવકાશ જટિલતા

ઓ (એન) કારણ કે આ પ્રોગ્રામ ફરીથી બદલી શકાય તેવા એરે અને હેશમેપમાં n તત્વો માટે જગ્યાનો ઉપયોગ કરે છે, તેથી જગ્યા જટિલતા ઓ (એન) છે.

સંદર્ભ