சொல்லைச் சேர்த்துத் தேடுங்கள் - தரவு கட்டமைப்பு வடிவமைப்பு லீட்கோட்


சிரமம் நிலை நடுத்தர
பின்வாங்கல் வடிவமைப்பு சரம் ட்ரை

“சொல் மற்றும் தேடல் சொல் - தரவு கட்டமைப்பு வடிவமைப்பு லீட்கோட்” சிக்கல் புதியதை உருவாக்க அல்லது வடிவமைக்கும்படி கேட்கிறது தரவு அமைப்பு. ஒரு வார்த்தையைச் சேர்ப்பதற்கும் சேமிப்பதற்கும் மற்றும் தேடல் செயல்பாடு சொற்களிலிருந்து ஒரு வழக்கமான வெளிப்பாட்டைக் கூட தேடக்கூடிய சொற்களைத் தேடுவதற்கும் இது பயன்படுத்தப்படலாம்.

உதாரணமாக:

சரம் / சொல் = “ஏய்” வரைபடத்தில் சேமிக்கப்பட்டால், பின்வரும் செயல்பாடுகள் ஒரே வெளியீட்டைக் கொடுக்கும் -

1. தேடல் (..y).

2. தேடல் (.e.).

3. தேடல் (ம ..).

மேற்கூறிய அனைத்தும் செயல்பாடு அழைப்புகள் வெளியீடு உண்மையாக இருக்கும்.

சொல்லைச் சேர்த்துத் தேடுங்கள் - தரவு கட்டமைப்பு வடிவமைப்பு லீட்கோட்

உதாரணமாக

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

சொல் மற்றும் தேடலுக்கான ஜாவா குறியீடு - தரவு கட்டமைப்பு வடிவமைப்பு லீட்கோட்

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 என்பது தேட வேண்டிய சொற்களின் நீளம்.

விண்வெளி சிக்கலானது

ஓ (n) ஏனெனில் இந்த நிரல் மறுஅளவிடத்தக்க வரிசை மற்றும் ஹாஷ்மாப்பில் உள்ள n உறுப்புகளுக்கு இடத்தைப் பயன்படுத்துகிறது, எனவே இட சிக்கலானது O (n) ஆகும்.

குறிப்புகள்