പദം ചേർത്ത് തിരയുക - ഡാറ്റ ഘടന രൂപകൽപ്പന ലീറ്റ്കോഡ്


വൈഷമ്യ നില മീഡിയം
ബാക്ക്ട്രാക്കിംഗ് ഡിസൈൻ സ്ട്രിംഗ് ട്രൈ

“വേഡ് ചേർക്കുക, തിരയുക - ഡാറ്റാ സ്ട്രക്ചർ ഡിസൈൻ ലീറ്റ്കോഡ്” എന്ന പ്രശ്നം പുതിയത് സൃഷ്ടിക്കാനോ രൂപകൽപ്പന ചെയ്യാനോ ആവശ്യപ്പെടുന്നു ഡാറ്റ ഘടന. ഒരു വാക്ക് ചേർക്കുന്നതിനോ സംഭരിക്കുന്നതിനോ തിരയൽ ഫംഗ്ഷന് വാക്കുകളിൽ നിന്ന് ഒരു സാധാരണ പദപ്രയോഗം പോലും തിരയാൻ കഴിയുന്ന പദങ്ങൾ തിരയുന്നതിനോ ഉപയോഗിക്കാവുന്നവ.

ഉദാഹരണത്തിന് :

സ്ട്രിംഗ് / വേഡ് = “ഹേയ്” മാപ്പിൽ സംഭരിച്ചിട്ടുണ്ടെങ്കിൽ, ഇനിപ്പറയുന്ന ഫംഗ്ഷനുകൾ സമാന output ട്ട്പുട്ട് നൽകും -

1. തിരയൽ (..y).

2. തിരയൽ (.e.).

3. തിരയൽ (h ..).

മുകളിലുള്ള മൂന്ന് ഫംഗ്ഷൻ കോളുകൾ output ട്ട്‌പുട്ട് ശരിയാകാൻ കാരണമാകും.

പദം ചേർത്ത് തിരയുക - ഡാറ്റ ഘടന രൂപകൽപ്പന ലീറ്റ്കോഡ്

ഉദാഹരണം

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. അതിനുശേഷം, വലുപ്പം മാറ്റാൻ ആരംഭിക്കുക ശ്രേണി സ്ട്രിംഗ് തരവും a ഹാഷ്‌മാപ്പ് സ്ട്രിംഗിന്റെ ജോഡിയുടെ തരവും പൂർണ്ണസംഖ്യയും.
  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

വേഡ് ചേർക്കാനും തിരയാനുമുള്ള ജാവ കോഡ് - ഡാറ്റാ സ്ട്രക്ചർ ഡിസൈൻ ലീറ്റ്കോഡ്

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

വേഡ് ചേർക്കാനും തിരയാനുമുള്ള സങ്കീർണ്ണത വിശകലനം - ഡാറ്റ ഘടന രൂപകൽപ്പന ലീറ്റ്കോഡ്

സമയ സങ്കീർണ്ണത

O (n * m) ഇവിടെ n എന്നത് ചേർത്ത പദങ്ങളുടെ എണ്ണവും m എന്നത് തിരയേണ്ട പദങ്ങളുടെ ദൈർഘ്യവുമാണ്.

ബഹിരാകാശ സങ്കീർണ്ണത

O (n) കാരണം ഈ പ്രോഗ്രാം വലുപ്പം മാറ്റാവുന്ന അറേയിലെയും ഹാഷ്‌മാപ്പിലെയും n ഘടകങ്ങൾക്ക് ഇടം ഉപയോഗിക്കുന്നു, അതിനാൽ സ്ഥല സങ്കീർണ്ണത O (n) ആണ്.

അവലംബം